oj.uz

Submission #771478

# Submission time Handle Problem Language Result Execution time Memory
771478 2023-07-03T04:26:32 Z Blistering_Barnacles Necklace (Subtask 1-3) (BOI19_necklace1) C++11
17 / 85
 198 ms 225092 KB 
//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)) ; 
    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}}) ;
        }
    }
    cout << ans.F << endl << ans.S.F << " "  << ans.S.S << endl ; 
}
int main(){
    fast ;
    q = 1 ;
    //cin >> q ;
    while(q--){
        solve() ;
    }
}

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14804 KB Output is correct
2 Correct 10 ms 14792 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Partially correct 9 ms 14788 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14804 KB Output is correct
2 Correct 10 ms 14792 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Partially correct 9 ms 14788 KB Output is partially correct
6 Correct 13 ms 21868 KB Output is correct
7 Partially correct 12 ms 21844 KB Output is partially correct
8 Correct 12 ms 21188 KB Output is correct
9 Partially correct 12 ms 21524 KB Output is partially correct
10 Correct 13 ms 21844 KB Output is correct
11 Partially correct 13 ms 21844 KB Output is partially correct
12 Partially correct 12 ms 21460 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14804 KB Output is correct
2 Correct 10 ms 14792 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Partially correct 9 ms 14788 KB Output is partially correct
6 Correct 13 ms 21868 KB Output is correct
7 Partially correct 12 ms 21844 KB Output is partially correct
8 Correct 12 ms 21188 KB Output is correct
9 Partially correct 12 ms 21524 KB Output is partially correct
10 Correct 13 ms 21844 KB Output is correct
11 Partially correct 13 ms 21844 KB Output is partially correct
12 Partially correct 12 ms 21460 KB Output is partially correct
13 Correct 198 ms 225092 KB Output is correct
14 Correct 175 ms 225040 KB Output is correct
15 Partially correct 168 ms 217452 KB Output is partially correct
16 Correct 161 ms 224384 KB Output is correct
17 Correct 148 ms 221296 KB Output is correct
18 Correct 163 ms 224228 KB Output is correct
19 Correct 192 ms 224116 KB Output is correct
20 Correct 165 ms 221132 KB Output is correct
21 Partially correct 171 ms 222268 KB Output is partially correct