oj.uz

Submission #377028

# Submission time Handle Problem Language Result Execution time Memory
377028 2021-03-12T19:15:17 Z Sara Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 675 ms 106988 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, 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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 106732 KB Output is correct
2 Correct 83 ms 106732 KB Output is correct
3 Correct 84 ms 106732 KB Output is correct
4 Correct 85 ms 106732 KB Output is correct
5 Correct 90 ms 106732 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 106732 KB Output is correct
2 Correct 83 ms 106732 KB Output is correct
3 Correct 84 ms 106732 KB Output is correct
4 Correct 85 ms 106732 KB Output is correct
5 Correct 90 ms 106732 KB Output is correct
6 Correct 90 ms 106988 KB Output is correct
7 Correct 88 ms 106860 KB Output is correct
8 Correct 86 ms 106732 KB Output is correct
9 Correct 89 ms 106732 KB Output is correct
10 Correct 88 ms 106860 KB Output is correct
11 Correct 89 ms 106732 KB Output is correct
12 Correct 88 ms 106860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 106732 KB Output is correct
2 Correct 83 ms 106732 KB Output is correct
3 Correct 84 ms 106732 KB Output is correct
4 Correct 85 ms 106732 KB Output is correct
5 Correct 90 ms 106732 KB Output is correct
6 Correct 90 ms 106988 KB Output is correct
7 Correct 88 ms 106860 KB Output is correct
8 Correct 86 ms 106732 KB Output is correct
9 Correct 89 ms 106732 KB Output is correct
10 Correct 88 ms 106860 KB Output is correct
11 Correct 89 ms 106732 KB Output is correct
12 Correct 88 ms 106860 KB Output is correct
13 Correct 666 ms 106860 KB Output is correct
14 Correct 671 ms 106860 KB Output is correct
15 Correct 657 ms 106860 KB Output is correct
16 Correct 675 ms 106896 KB Output is correct
17 Correct 629 ms 106860 KB Output is correct
18 Correct 662 ms 106808 KB Output is correct
19 Correct 657 ms 106860 KB Output is correct
20 Correct 649 ms 106860 KB Output is correct
21 Correct 656 ms 106988 KB Output is correct