oj.uz

Submission #377027

# Submission time Handle Problem Language Result Execution time Memory
377027 2021-03-12T18:58:52 Z Sara Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 82 ms 106732 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back

const int N = 3000 + 10;
const int SQ = 100;
const int LOG = 25;
const int MOD = 1e9 + 7;
const ll  inf = 1e9 + 5;

int n, m;
string a, b;
int suf[N][N];
int mx_sufA_preB[N][N];
int mx_preA_sufB[N][N];
int ans;
int mx[N];

inline void solve(){

    for (int i = 0; i < N; i ++){
        for (int j = 0; j < N; j ++){
            suf[i][j] = 0;
            mx_preA_sufB[i][j] = 0;
            mx_sufA_preB[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            if (a[i] == b[j]){
                suf[i][j] = suf[i - 1][j - 1] + 1;
            }
            else {
                suf[i][j] = 0;
            }
        }
    }

    for (int i = 1; i <= n; i ++){
        fill(mx + 1, mx + m + 1, 0);
        for (int j = 1; j <= m; j ++){
            if (suf[i][j] == 0) continue;
            int id = j - suf[i][j] + 1;
            assert(1 <= id && id <= m);
            mx[id] = max(mx[id], j);
        }
        int cur = 0;
        for (int j = 1; j <= m; j ++){
            cur = max(cur, mx[j]);
            mx_sufA_preB[i][j] = max(0, cur - j + 1);
        }
    }

    for (int i = 1; i <= m; i ++){
        fill(mx + 1, mx + n + 1, 0);
        for (int j = 1; j <= n; j ++){
            if (suf[j][i] == 0) continue;
            int id = j - suf[j][i] + 1;
            assert(1 <= id && id <= n);
            mx[id] = max(mx[id], j);
        }
        int cur = 0;
        for (int j = 1; j <= n; j ++){
            cur = max(cur, mx[j]);
            mx_preA_sufB[j][i] = max(0, cur - j + 1);
        }
    }

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            if (a[i] == b[j]){
                ans = max(ans, mx_preA_sufB[i][j] + mx_sufA_preB[i][j] - 1);
            }
            if (1 < i && 1 < j){
                ans = max(ans, mx_sufA_preB[i - 1][j] + mx_preA_sufB[i][j - 1]);
            }
        }
    }

    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0);
    cin >> a >> b;
    n = a.size(); m = b.size();

    string tmp = a;
    reverse(tmp.begin(), tmp.end());

    a = ' ' + a;  b = ' ' + b;
    solve(); 
    a = tmp; a = ' ' + a; 
    solve();
    cout << ans << '\n';
    return 0;
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 106732 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 106732 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 106732 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -