Submission #526477

#	Time	Username	Problem	Language	Result	Execution time	Memory
526477		ali22413836	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	85 / 85	345 ms	211780 KiB

necklace

#include <bits/stdc++.h>
#define endl "\n"
typedef long long ll ;
using namespace std;

string str, str2 ;
ll n , m , dp1[3001][3001] , dp2[3001][3001] , lcs[3001][3001]  ;
array <ll, 3> ans = {0, 0, 0};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> str >> str2;
    ll n = str.size();
    ll m = str2.size();
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            lcs[i][j] = str[i] == str2[j] ? ((i > 0 && j > 0 ? lcs[i - 1][j - 1] : 0) + 1) : 0;
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            if (lcs[i][j] > 0){
                dp1[i][j - lcs[i][j] + 1] = max(dp1[i][j - lcs[i][j] + 1], lcs[i][j]);
                dp2[i - lcs[i][j] + 1][j] = max(dp2[i - lcs[i][j] + 1][j], lcs[i][j]);
            }
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            if (j > 0) dp1[i][j] = max(dp1[i][j], dp1[i][j - 1] - 1);
            if (i > 0) dp2[i][j] = max(dp2[i][j], dp2[i - 1][j] - 1);
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            ll le = dp1[i][j] + (i + 1 < n && j > 0 ? dp2[i + 1][j - 1] : 0);
            if (le > 0){
                    ans = max(ans ,  {le, i - dp1[i][j] + 1, j + dp1[i][j] - le}) ;
            }
        }
    }
    for(ll i = 0 ; i < 3000 ; i++){
        for(ll j = 0 ; j < 3000; j++){
            dp1[i][j] = dp2[i][j] = lcs[i][j] = 0 ;
        }
    }
    reverse(begin(str2), end(str2));
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            lcs[i][j] = str[i] == str2[j] ? ((i > 0 && j > 0 ? lcs[i - 1][j - 1] : 0) + 1) : 0;
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            if (lcs[i][j] > 0){
                dp1[i][j - lcs[i][j] + 1] = max(dp1[i][j - lcs[i][j] + 1], lcs[i][j]);
                dp2[i - lcs[i][j] + 1][j] = max(dp2[i - lcs[i][j] + 1][j], lcs[i][j]);
            }
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            if (j > 0) dp1[i][j] = max(dp1[i][j], dp1[i][j - 1] - 1);
            if (i > 0) dp2[i][j] = max(dp2[i][j], dp2[i - 1][j] - 1);
        }
    }
    for (ll i = 0; i < n; i++){
        for (ll j = 0; j < m; j++){
            ll le = dp1[i][j] + (i + 1 < n && j > 0 ? dp2[i + 1][j - 1] : 0);
            if (le > 0){
                    ans = max(ans , {le, i - dp1[i][j] + 1, (str2.size()) - (j + dp1[i][j] - le) - le}) ;
            }
        }
    }
    cout << ans[0] << " " << ans[1] << " " << ans[2] << endl  ;
    return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:70:98: warning: narrowing conversion of '((((long long unsigned int)str2.std::__cxx11::basic_string<char>::size()) - ((long long unsigned int)((j + dp1[i][j]) - le))) - ((long long unsigned int)le))' from 'long long unsigned int' to 'long long int' [-Wnarrowing]
   70 |                     ans = max(ans , {le, i - dp1[i][j] + 1, (str2.size()) - (j + dp1[i][j] - le) - le}) ;
      |                                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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