oj.uz

Submission #676945

# Submission time Handle Problem Language Result Execution time Memory
676945 2023-01-01T17:24:12 Z _martynas Necklace (Subtask 1-3) (BOI19_necklace1) C++11
85 / 85
 361 ms 106408 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 << " " << ans_j << "\n";

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 2132 KB Output is correct
7 Correct 5 ms 2132 KB Output is correct
8 Correct 6 ms 1900 KB Output is correct
9 Correct 6 ms 2096 KB Output is correct
10 Correct 5 ms 2120 KB Output is correct
11 Correct 6 ms 2168 KB Output is correct
12 Correct 6 ms 2020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 2132 KB Output is correct
7 Correct 5 ms 2132 KB Output is correct
8 Correct 6 ms 1900 KB Output is correct
9 Correct 6 ms 2096 KB Output is correct
10 Correct 5 ms 2120 KB Output is correct
11 Correct 6 ms 2168 KB Output is correct
12 Correct 6 ms 2020 KB Output is correct
13 Correct 343 ms 106408 KB Output is correct
14 Correct 300 ms 106300 KB Output is correct
15 Correct 361 ms 100200 KB Output is correct
16 Correct 302 ms 104572 KB Output is correct
17 Correct 254 ms 102560 KB Output is correct
18 Correct 260 ms 105532 KB Output is correct
19 Correct 302 ms 105272 KB Output is correct
20 Correct 320 ms 102440 KB Output is correct
21 Correct 324 ms 103524 KB Output is correct