Submission #676945

#	Time	Username	Problem	Language	Result	Execution time	Memory
676945		_martynas	Necklace (Subtask 1-3) (BOI19_necklace1)	C++11	85 / 85	361 ms	106408 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int n, m;
string a, b;

tuple<int, int, int> solve() {
    vector<vi> l_ss(n, vi(m));
    vector<vi> l_sp(n, vi(m));
    vector<vi> l_ps(n, vi(m));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(a[i] == b[j]) l_ss[i][j] = i && j ? l_ss[i-1][j-1]+1 : 1;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(l_ss[i][j]) l_sp[i][j-l_ss[i][j]+1] = max(l_sp[i][j-l_ss[i][j]+1], l_ss[i][j]);
            if(j) l_sp[i][j] = max(l_sp[i][j], l_sp[i][j-1]-1);

            if(l_ss[i][j]) l_ps[i-l_ss[i][j]+1][j] = max(l_ps[i-l_ss[i][j]+1][j], l_ss[i][j]);
            if(i) l_ps[i][j] = max(l_ps[i][j], l_ps[i-1][j]-1);
        }
    }

    int mx = 0;
    int si = 0, sj = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
        if(l_ss[i][j] > mx) {
            mx = l_ss[i][j];
            si = i-mx+1, sj = j-mx+1;
        }
    }
    for(int i = 0; i+1 < n; i++) for(int j = 0; j+1 < m; j++) {
        int len = l_sp[i][j+1]+l_ps[i+1][j];
        if(len > mx) {
            mx = len;
            si = i-l_sp[i][j+1]+1, sj = j-l_ps[i+1][j]+1;
        }
    }
    return {mx, si, sj};
}

int main() {
    cin >> a >> b; n = a.size(), m = b.size();
    int ans_len, ans_i, ans_j;
    int len, i, j;
    tie(ans_len, ans_i, ans_j) = solve();
    reverse(b.begin(), b.end());
    tie(len, i, j) = solve();

    if(len > ans_len) {
        ans_len = len;
        ans_i = i;
        ans_j = m-(j+len-1)-1; // (rotated)
    }

    cout << ans_len << "\n";
    cout << ans_i << " " << ans_j << "\n";

    return 0;
}

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