oj.uz

Submission #518768

# Submission time Handle Problem Language Result Execution time Memory
518768 2022-01-24T14:51:08 Z K4YAN Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 1 ms 1228 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];
            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];
            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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 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 1228 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 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -