oj.uz

Submission #518771

# Submission time Handle Problem Language Result Execution time Memory
518771 2022-01-24T14:57:36 Z K4YAN Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 402 ms 141968 KB 
//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const int mxn = 3e3 + 16;
ll n, m, q;
ll dp[mxn][mxn], pd[mxn][mxn];
string s, h;

void input() {

    cin >> s >> h;

}

void solve() {

    n = int(s.size()), m = int(h.size());
    for(int i = n - 1; i > -1; i--) {
        for(int j = m - 1; j > -1; j--) {
            if(s[i] == h[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
            else dp[i][j] = 0;
        }
    }
    int green_ptr = 0, red_ptr = 0;
    for(int i = 0; i < m; i++) {
        green_ptr = red_ptr = 0;
        while(red_ptr < n) {
            while(green_ptr + dp[green_ptr][i] <= red_ptr) {
                green_ptr++;
            }
            if(green_ptr > red_ptr) {
                pd[red_ptr][i] = 0; red_ptr++;
                continue;
            }
            pd[red_ptr][i] = red_ptr - green_ptr + 1;
            red_ptr++;
        }
    }

    ll ans = 0, sum = 0, sum2 = 0, st1, st2;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sum = dp[i][j];
            if(i == 0) {
                sum2 = 0;
            } else {
                sum2 = pd[i - 1][j + sum];
            }
            sum += sum2;
            if(sum > ans) {
                ans = sum, st1 = i - sum2, st2 = j;
            }
        }
    }
    reverse(all(h));
    for(int i = n - 1; i > -1; i--) {
        for(int j = m - 1; j > -1; j--) {
            if(s[i] == h[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
            else dp[i][j] = 0;
        }
    }
    for(int i = 0; i < m; i++) {
        green_ptr = red_ptr = 0;
        while(red_ptr < n) {
            while(green_ptr + dp[green_ptr][i] <= red_ptr) {
                green_ptr++;
            }
            if(green_ptr > red_ptr) {
                pd[red_ptr][i] = 0; red_ptr++;
                continue;
            }
            pd[red_ptr][i] = red_ptr - green_ptr + 1;
            red_ptr++;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sum = dp[i][j];
            if(i == 0) {
                sum2 = 0;
            } else {
                sum2 = pd[i - 1][j + sum];
            }
            sum += sum2;
            if(sum > ans) {
                ans = sum, st1 = i - sum2, st2 = m - j - sum;
            }
        }
    }
    cout << ans << "\n" << st1 << " " << st2 << endl;
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}

Compilation message

necklace.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      |

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1212 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1212 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1220 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5708 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 5 ms 5836 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1212 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1220 KB Output is correct
6 Correct 5 ms 5964 KB Output is correct
7 Correct 4 ms 5964 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5708 KB Output is correct
10 Correct 5 ms 5964 KB Output is correct
11 Correct 5 ms 5836 KB Output is correct
12 Correct 4 ms 5580 KB Output is correct
13 Correct 402 ms 141956 KB Output is correct
14 Correct 382 ms 141968 KB Output is correct
15 Correct 398 ms 137044 KB Output is correct
16 Correct 378 ms 141512 KB Output is correct
17 Correct 389 ms 139336 KB Output is correct
18 Correct 390 ms 141512 KB Output is correct
19 Correct 379 ms 141256 KB Output is correct
20 Correct 387 ms 139208 KB Output is correct
21 Correct 359 ms 139976 KB Output is correct