Submission #518771

#	Time	Username	Problem	Language	Result	Execution time	Memory
518771		K4YAN	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	402 ms	141968 KiB

necklace

//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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40