oj.uz

Submission #646201

# Submission time Handle Problem Language Result Execution time Memory
646201 2022-09-29T07:00:33 Z mychecksedad Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 47428 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, m, ans = 0, p, q, dp[5000][5000];
string a, b;
void f(string &s, string &t, bool tp){    
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(s[i] == t[j]){
                if(i==0||j==0) dp[i][j] = 1;
                else dp[i][j] = dp[i - 1][j - 1] + 1;
            }else dp[i][j] = 0;
        }
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            int x = j - dp[i][j];
            if(ans < dp[i][j]){
                ans = dp[i][j];
                p = i - dp[i][j] + 1;
                if(!tp)
                    q = j - dp[i][j] + 1;
                else
                    q = m - j - 1;
            }
            if(x < 0) continue;
            for(int d = 1; i + d < n; ++d){
                if(dp[i + d][x] < d) continue;
                if(ans < d + dp[i][j]){
                    ans = d + dp[i][j];
                    p = i - dp[i][j] + 1;
                    if(!tp)
                        q = x - d + 1;
                    else
                        q = m - j - 1;
                    // cout << i + d << ' ' << d << ' ' << dp[i][j] << ' ' << dp[i + d][x] <<  ' ' << x << '\n';
                }
            }
        }
    }
}

void solve(){
    cin >> a >> b;
    n = a.length();
    m = b.length();
    f(a, b, 0);
    reverse(all(b));
    f(a, b, 1);
    cout << ans << '\n';
    if(ans > 0) cout << p << ' ' << q;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:72:16: warning: unused variable 'aa' [-Wunused-variable]
   72 |     int T = 1, aa;
      |                ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 2 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 74 ms 2548 KB Output is correct
7 Correct 75 ms 2636 KB Output is correct
8 Correct 48 ms 2388 KB Output is correct
9 Correct 52 ms 2440 KB Output is correct
10 Correct 50 ms 2516 KB Output is correct
11 Correct 53 ms 2516 KB Output is correct
12 Correct 50 ms 2388 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 74 ms 2548 KB Output is correct
7 Correct 75 ms 2636 KB Output is correct
8 Correct 48 ms 2388 KB Output is correct
9 Correct 52 ms 2440 KB Output is correct
10 Correct 50 ms 2516 KB Output is correct
11 Correct 53 ms 2516 KB Output is correct
12 Correct 50 ms 2388 KB Output is correct
13 Execution timed out 1579 ms 47428 KB Time limit exceeded
14 Halted 0 ms 0 KB -