/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 588.0 KiB
#2 Accepted 4ms 332.0 KiB
#3 Accepted 4ms 332.0 KiB
#4 Accepted 3ms 652.0 KiB
#5 Accepted 3ms 796.0 KiB
#6 Accepted 4ms 1.328 MiB
#7 Accepted 10ms 8.27 MiB
#8 Accepted 9ms 8.562 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
#define all(x) x.begin(), x.end()
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5 + 19;
string x = "seriousOJ";

void solve() {
    int n;
    cin >> n;
    string s1, s2 = "SeriousOJ";
    cin >> s1;


    int m = s2.size();

    int dp[n + 1][m + 1];
    for(int i = 0; i <= n; i++) dp[i][0] = 0;
    for(int i = 0; i <= m; i++) dp[0][i] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        //cout << i << ' ' << j << endl;
        if (s1[i - 1] == s2[j - 1]) {
            lcs = s1[i - 1] + lcs;
            i--, j--;
        } 
        else if (dp[i - 1][j] > dp[i][j - 1]) i--;
        else j--;            
    }

    if(lcs == s2) cout << "YES" << endl;
    else cout << "NO" << endl;
}

signed main()
{
    FAST
    
    int T = 1;
    cin >> T;
    for(int tt = 1; tt <= T; tt++) {
        //cout << "Case " << tt << ": ";
        solve();
    }
    return 0;
    
}

Information

Submit By
Type
Submission
Problem
P1147 SeriousOJ Challenge
Contest
LU IUJPC : Sylhet Division 2024 Replay Contest
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-10 11:36:18
Judged At
2024-12-10 11:36:18
Judged By
Score
100
Total Time
10ms
Peak Memory
8.562 MiB