Submission #377028

#	Time	Username	Problem	Language	Result	Execution time	Memory
377028		Sara	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	85 / 85	675 ms	106988 KiB

necklace

#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, ansA, ansB;
int mx[N];

inline void solve(bool type){

    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]){
                if (ans < mx_preA_sufB[i][j] + mx_sufA_preB[i][j] - 1){
                    ans = mx_preA_sufB[i][j] + mx_sufA_preB[i][j] - 1;
                    ansB = j - mx_preA_sufB[i][j];
                    ansA = i - mx_sufA_preB[i][j];
                    if (type) ansA = n - ansA - ans;
                }
            }
            if (1 < i && 1 < j){
                if (ans < mx_sufA_preB[i - 1][j] + mx_preA_sufB[i][j - 1]){
                    ans = mx_sufA_preB[i - 1][j] + mx_preA_sufB[i][j - 1];
                    ansB = j - 1 - mx_preA_sufB[i][j - 1];
                    ansA = i - 1 - mx_sufA_preB[i - 1][j];
                    if (type) ansA = n - ansA - ans;
                }
            }
        }
    }

    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(0); 
    a = tmp; a = ' ' + a; 
    solve(1);
    cout << ans << '\n' << ansA << ' ' << ansB << '\n';
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40