Submission #733278

#TimeUsernameProblemLanguageResultExecution timeMemory
733278kymCopy and Paste 3 (JOI22_copypaste3)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i,s,e) for(int i = s; i <= (int)e; ++i) #define DEC(i,s,e) for(int i = s; i >= (int)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define reach #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <int, int> pi; typedef tuple<int,int,int> ti3; typedef tuple<int,int,int,int> ti4; int rand(int a, int b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (long long)1e18 + 500; template <typename T> void chmax(T& a, const T b) { a=max(a,b); } template <typename T> void chmin(T& a, const T b) { a=min(a,b); } const int MAXN = 2505; int H[MAXN][MAXN]; int n; int A,B,C; int s[MAXN]; int T[MAXN]; int qexp(int a, int b, int mod){ int res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod; b>>=1; } return res; } unordered_map<int,vector<pi>> V; unordered_map<int,int> dp2; int dpdp(int l, int r); int imp; int transit(int hash){ if(dp2.find(hash)!=dp2.end())return dp2[hash]; if(hash==imp)reach vector<int> pts; vector<int> sts,ens; unordered_map<int,vector<int>> vv; for(auto seg:V[hash]){ sts.pb(seg.f-1); pts.pb(seg.f-1); pts.pb(seg.s); ens.pb(seg.s); } sort(all(sts)); sts.resize(unique(all(sts))-sts.begin()); sort(all(ens)); ens.resize(unique(all(ens))-ens.begin()); sort(all(pts)); pts.resize(unique(all(pts))-pts.begin()); for(auto seg:V[hash]){ int l=lower_bound(all(pts),seg.f-1)-pts.begin(); int r=lower_bound(all(pts),seg.s)-pts.begin(); vv[r].pb(l); } if(imp==hash){ dbv(sts); } int ans=oo; FOR(l,0,sts.size()-1){ vector<int> mn; int idx=0; unordered_map<int,int> mp; if(imp==hash)db(l); FOR(i,0,pts.size()-1){ if(pts[i]<sts[l])continue; if(pts[i]==sts[l]){ mp[pts[i]]=0; mn.pb(0); continue; } ++idx; mp[pts[i]]=idx; int val=oo; if(imp==hash){ dbv(vv[i]); } for(auto x:vv[i]){ if(pts[x]>=sts[l]) { chmin(val,mn[mp[pts[x]]]+C); } } chmin(val,mn.back()+A*(pts[i]-pts[i-1])); mn.pb(val); if(imp==hash){ dbv(mn); } if(pts[i]-sts[l]>=(V[hash][0].s-V[hash][0].f+1)*2)chmin(ans, val+dpdp(sts[l]+1,pts[i])); } } return dp2[hash]=ans; } int dp1[MAXN][MAXN]; int dpdp(int l, int r){ if(~dp1[l][r]) return dp1[l][r]; if(l==1&&r==n)return 0; int ans=oo; if(r!=n)chmin(ans,dpdp(l,r+1)+A); if(l!=1)chmin(ans,dpdp(l-1,r)+A); chmin(ans,transit(H[l][r])+B); //db3(l,r,ans); return dp1[l][r]=ans; } int32_t main() { IAMSPEED memset(dp1,-1,sizeof dp1); cin >> n; FOR(i,1,n){ char ch; cin >> ch; s[i]=ch-'a'+1; } cin >> A >> B >> C; FOR(i,1,n){ int val=qexp(27,i,MOD)*s[i]; T[i]=T[i-1]+val; } FOR(i,1,n){ FOR(j,i,n){ int d=qexp(27,i-1,MOD); H[i][j]=((T[j]-T[i-1]+MOD)%MOD)*qexp(d,MOD-2,MOD)%MOD; V[H[i][j]].pb({i,j}); } } //imp=H[2][4]; //cerr<<transit(H[2][4]); //exit(0); int ans=oo; FOR(i,1,n){ int res=dpdp(i,i)+A; db2(i,res); chmin(ans,res); } cout<<ans; }

Compilation message (stderr)

copypaste3.cpp: In function 'long long int transit(long long int)':
copypaste3.cpp:72:3: error: 'pts' was not declared in this scope; did you mean 'sts'?
   72 |   pts.pb(seg.f-1);
      |   ^~~
      |   sts
copypaste3.cpp:82:11: error: 'pts' was not declared in this scope; did you mean 'sts'?
   82 |  sort(all(pts));
      |           ^~~
copypaste3.cpp:27:17: note: in definition of macro 'all'
   27 | #define all(x) (x).begin(), (x).end()
      |                 ^