oj.uz

답안 #722380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722380 2023-04-11T21:19:05 Z urosk 원형 문자열 (IZhO13_rowords) C++14
100 / 100
 1970 ms 53312 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
*/
/*
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 4005
ll n,m;
ll dpl[maxn][maxn],dpu[maxn][maxn];
string a,b;
void upd(string a,string b,ll x,ll y){
    ll c = (a[x-1]==b[y-1])|dpu[x][y-1]|dpl[x-1][y];
    dpl[x][y] = c-dpu[x][y-1];
    dpu[x][y] = c-dpl[x-1][y];
}
ll reshi(string a,string b){
    b+=b;
    n = a.size();
    m = b.size();
    for(ll i = 0;i<=n;i++) for(ll j = 0;j<=m;j++) dpu[i][j] = dpl[i][j] = 0;
    for(ll i = 1;i<=n;i++) for(ll j = 1;j<=m;j++) upd(a,b,i,j);
    ll ans = 0;
    for(ll i = 1;i<=n;i++) ans+=dpu[i][m/2];
    for(ll j = 1;j<m/2;j++){
        for(ll x = 1,y = j;x<=n&&y<=m;){
            ll last = dpu[x][y];
            if(j==y) dpu[x][y] = 0;
            else upd(a,b,x,y);
            if(last==dpu[x][y]) x++;
            else y++;
        }
        ll cur = 0;
        for(ll i = 1;i<=n;i++) cur+=dpu[i][j+m/2];
        ans = max(ans,cur);
    }
    return ans;
}
void tc(){
    cin >> a >> b;
    ll ans = reshi(a,b);
    reverse(all(b));
    ans = max(ans,reshi(a,b));
    cout<<ans<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}
/**
algorithm
grammar
4
**/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 47 ms 11476 KB Output is correct
7 Correct 619 ms 39728 KB Output is correct
8 Correct 1330 ms 39732 KB Output is correct
9 Correct 1205 ms 39728 KB Output is correct
10 Correct 1141 ms 39724 KB Output is correct
11 Correct 1264 ms 43652 KB Output is correct
12 Correct 1815 ms 50228 KB Output is correct
13 Correct 1786 ms 50232 KB Output is correct
14 Correct 1458 ms 45444 KB Output is correct
15 Correct 1970 ms 53184 KB Output is correct
16 Correct 1635 ms 43580 KB Output is correct
17 Correct 978 ms 37936 KB Output is correct
18 Correct 1728 ms 53312 KB Output is correct
19 Correct 1071 ms 39736 KB Output is correct
20 Correct 1463 ms 47648 KB Output is correct
21 Correct 198 ms 22100 KB Output is correct
22 Correct 361 ms 29008 KB Output is correct
23 Correct 548 ms 34644 KB Output is correct
24 Correct 608 ms 36544 KB Output is correct
25 Correct 863 ms 44748 KB Output is correct