oj.uz

답안 #722379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722379 2023-04-11T21:16:30 Z urosk 원형 문자열 (IZhO13_rowords) C++14
20 / 100
 1615 ms 53332 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
20.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 2 ms 724 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Incorrect 43 ms 11572 KB Output isn't correct
7 Correct 1028 ms 39836 KB Output is correct
8 Incorrect 1062 ms 39736 KB Output isn't correct
9 Incorrect 1049 ms 39728 KB Output isn't correct
10 Incorrect 1027 ms 39732 KB Output isn't correct
11 Incorrect 1187 ms 43664 KB Output isn't correct
12 Incorrect 1493 ms 50240 KB Output isn't correct
13 Incorrect 1586 ms 50236 KB Output isn't correct
14 Incorrect 1218 ms 45444 KB Output isn't correct
15 Incorrect 1615 ms 53180 KB Output isn't correct
16 Incorrect 1275 ms 43580 KB Output isn't correct
17 Incorrect 646 ms 37944 KB Output isn't correct
18 Incorrect 1384 ms 53332 KB Output isn't correct
19 Incorrect 1054 ms 39732 KB Output isn't correct
20 Incorrect 1206 ms 47648 KB Output isn't correct
21 Incorrect 148 ms 22072 KB Output isn't correct
22 Incorrect 268 ms 29008 KB Output isn't correct
23 Incorrect 419 ms 34644 KB Output isn't correct
24 Incorrect 426 ms 36556 KB Output isn't correct
25 Incorrect 601 ms 44704 KB Output isn't correct