Submission #771486

#TimeUsernameProblemLanguageResultExecution timeMemory
771486Blistering_BarnaclesNecklace (Subtask 1-3) (BOI19_necklace1)C++11
85 / 85
350 ms225536 KiB
//Billions of bilious blue blistering barnacles in a thundering typhoon! #ifndef LOCAL #pragma GCC optimize("Ofast,fast-math,unroll-loops") #pragma GCC target("avx2,fma") #endif #include<bits/stdc++.h> #define fast ios::sync_with_stdio(0) , cin.tie(0) #define F first #define S second #define pb push_back #define vll vector< ll > #define vi vector< int > #define pll pair< ll , ll > #define pi pair< int , int > #define all(s) s.begin() , s.end() #define sz(s) s.size() #define str string #define md ((s + e) / 2) #define mid ((l + r) / 2) #define msdp(dp) memset(dp , -1 , sizeof dp) #define mscl(dp) memset(dp , 0 , sizeof dp) #define C continue #define R return #define B break #define lx node * 2 #define rx node * 2 + 1 #define br(dosomething) {dosomething; break;} #define co(dosomething) {dosomething ; continue;} using namespace std; typedef long long ll; ll q, a[555555] , b[555555] , dp[555555] , k, l, m, n, o, p; map < ll , ll > mp ; vll adj[555555]; const ll mod = 1e9+7; ll Lss[3005][3005] , Lsp[3005][3005] , Lps[3005][3005] ; str s , t ; void solve(){ cin >> s >> t ; n = sz(s) , m = sz(t) ; reverse(all(t)) ; str op = t ; s = ' ' + s , t = ' ' + t ; for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ Lss[i][j] = (s[i] == t[j] ? 1 + Lss[i - 1][j - 1] : 0) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ if(!Lss[i][j])C ; Lsp[i][j - Lss[i][j] + 1] = max(Lsp[i][j - Lss[i][j] + 1] , Lss[i][j]) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ if(!Lss[i][j])C ; Lps[i - Lss[i][j] + 1][j] = max(Lps[i - Lss[i][j] + 1][j] , Lss[i][j]) ; } } pair < ll , pll > ans = {0 , {0 , 0}} ; for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ Lsp[i][j] = max(Lsp[i][j] , Lsp[i][j - 1] - 1) ; Lps[i][j] = max(Lps[i][j] , Lps[i - 1][j] - 1) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ ans = max(ans , {Lsp[i][j] + Lps[i + 1][j - 1] , {i - Lsp[i][j] , m - j - Lsp[i][j] + 1}}) ; } } reverse(all(op)) ; t = op ; t = ' ' + t ; mscl(Lss) , mscl(Lsp) , mscl(Lps) ; for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ Lss[i][j] = (s[i] == t[j] ? 1 + Lss[i - 1][j - 1] : 0) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ if(!Lss[i][j])C ; Lsp[i][j - Lss[i][j] + 1] = max(Lsp[i][j - Lss[i][j] + 1] , Lss[i][j]) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ if(!Lss[i][j])C ; Lps[i - Lss[i][j] + 1][j] = max(Lps[i - Lss[i][j] + 1][j] , Lss[i][j]) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ Lsp[i][j] = max(Lsp[i][j] , Lsp[i][j - 1] - 1) ; Lps[i][j] = max(Lps[i][j] , Lps[i - 1][j] - 1) ; } } for(ll i = 1 ; i <= n ; i++){ for(ll j = 1 ; j <= m ; j++){ ans = max(ans , {Lsp[i][j] + Lps[i + 1][j - 1] , {i - Lsp[i][j] , j - Lps[i + 1][j - 1] - 1}}) ; } } cout << ans.F << endl << ans.S.F << " " << ans.S.S << endl ; } int main(){ fast ; q = 1 ; //cin >> q ; while(q--){ solve() ; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...