Submission #965210

#TimeUsernameProblemLanguageResultExecution timeMemory
965210vjudge1Copy and Paste 3 (JOI22_copypaste3)C++17
62 / 100
3070 ms108040 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 ll 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; const int L=3; struct hash{ ll mod,C; ll 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]*1ll*C+s[i])%mod; p[i]=p[i-1]*1ll*C%mod; } } int get(int l,int r){ return (h[r]-h[l-1]*1ll*p[r-l+1]%mod+mod)%mod; } }H[L]; ll dp[MAX][MAX]; int last[MAX][MAX]; map<pii,int> was; struct segtree{ ll t[4*MAX]; int p[MAX]; void build(int v,int tl,int tr){ t[v]=inf; if(tl==tr){ p[tl]=v; return; } int tm=(tl+tr)/2; build(2*v,tl,tm); build(2*v+1,tm+1,tr); } void update(int pos,ll x){ int v=p[pos]; t[v]=x; v/=2; while(v){ t[v]=min(t[2*v],t[2*v+1]); v/=2; } } }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)}]=R; } int l=r-zs+1; if(was.count({H[0].get(l,r),H[1].get(l,r)})){ last[l][r]=was[{H[0].get(l,r),H[1].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); vector<ll> cost(r,0); for(int l=r-1;l>=1;l--){ cost[r-l]=dp[l+1][r]+c-a*1ll*(r-l); t.update(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*1ll*zs); t.update(zs,cost[zs]); if(last[l][l+zs-1]-zs+1>0)upd[last[l][l+zs-1]-zs+1].pb(zs); } dp[l][r]=min(dp[l][r-1]+a,t.t[1]+(r-l+1)*1ll*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...