oj.uz

Submission #676944

# Submission time Handle Problem Language Result Execution time Memory
676944 2023-01-01T17:21:09 Z _martynas Necklace (Subtask 1-3) (BOI19_necklace1) C++11
0 / 85
 1 ms 340 KB 
#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+1 << " " << ans_j+1 << "\n";

    return 0;
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -