Submission #965174

#TimeUsernameProblemLanguageResultExecution timeMemory
965174vjudge1Copy and Paste 3 (JOI22_copypaste3)C++17
62 / 100
3051 ms135840 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert #define int ll #define ull unsigned ll const int MAX=2500+15; const int B=331; const int maxB=1000; const int N=104; const int block=450; const int inf=1e13; const int mod=1e9+7; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,a,b,c; string s; struct hash{ int mod,C; int h[MAX],p[MAX]; void init(int module,int constant,string s){ mod=module; C=constant; p[0]=1; for(int i=1;i<sz(s);i++){ h[i]=(h[i-1]*C+s[i])%mod; p[i]=p[i-1]*C%mod; } } int get(int l,int r){ return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod; } }H[3]; bool isEqual(int l,int r,int L,int R){ for(int i=0;i<3;i++){ if(H[i].get(l,r)!=H[i].get(L,R))return 0; } return 1; } int dp[MAX][MAX]; int last[MAX][MAX]; map<pair<pii,int>,int> was; struct segtree{ int t[4*MAX]; void build(int v,int tl,int tr){ t[v]=inf; if(tl==tr){ return; } int tm=(tl+tr)/2; build(2*v,tl,tm); build(2*v+1,tm+1,tr); } void update(int v,int tl,int tr,int pos,int x){ if(tl==tr){ t[v]=x; return; } int tm=(tl+tr)/2; if(pos<=tm)update(2*v,tl,tm,pos,x); else update(2*v+1,tm+1,tr,pos,x); t[v]=min(t[2*v],t[2*v+1]); } }t; void solve(){ cin>>n>>s; cin>>a>>b>>c; s="#"+s; H[0].init(1e9+7,331,s); H[1].init(1e9+9,331,s); H[2].init(998244353,331,s); for(int zs=1;zs<=n;zs++){ for(int r=zs;r<=n;r++){ int R=r-zs; int L=R-zs+1; if(1<=L){ was[{{H[0].get(L,R),H[1].get(L,R)},H[2].get(L,R)}]=R; } int l=r-zs+1; if(was.count({{H[0].get(l,r),H[1].get(l,r)},H[2].get(l,r)})){ last[l][r]=was[{{H[0].get(l,r),H[1].get(l,r)},H[2].get(l,r)}]; } } } for(int i=1;i<=n;i++)dp[i][i]=a; for(int r=2;r<=n;r++){ t.build(1,1,r); vector<int> upd[r]; vector<int> cnt(r,0),cost(r,0); // multiset<int> st; for(int l=r-1;l>=1;l--){ cost[r-l]=dp[l+1][r]+c-a*(r-l); t.update(1,1,r,r-l,cost[r-l]); if(last[l+1][r]-(r-l)+1>0)upd[last[l+1][r]-(r-l)+1].pb(r-l); for(int zs:upd[l]){ cost[zs]+=(c-a*zs); t.update(1,1,r,zs,cost[zs]); if(last[l][l+zs-1]-zs+1>0)upd[last[l][l+zs-1]-zs+1].pb(zs); } // cout<<t.t[1]<<" "<<*st.begin()<<"\n"; dp[l][r]=min(dp[l][r-1]+a,t.t[1]+(r-l+1)*a+b); } } // for(int zs=1;zs<=n;zs++){ // for(int l=1;l+zs-1<=n;l++){ // cout<<dp[l][l+zs-1]<<" "; // } // cout<<"\n"; // } cout<<dp[1][n]<<"\n"; } signed main(){ // freopen("triangles.in","r",stdin); // freopen("triangles.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // prec(); int t=1; // cin>>t; while(t--)solve(); }

Compilation message (stderr)

copypaste3.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
copypaste3.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...