Submission #567981

#TimeUsernameProblemLanguageResultExecution timeMemory
567981jamezzzCopy and Paste 3 (JOI22_copypaste3)C++17
100 / 100
800 ms106764 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(), x.end() #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<pll> vll; mt19937 rng(time(0)); #define mod 1000000007 #define mod2 1000000009 inline int add(int a,int b){ int r=a+b; while(r>=mod)r-=mod; while(r<0)r+=mod; return r; } inline int mult(int a,int b){ return (int)(((ll)(a*b))%mod); } inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } int n,a,b,c,cnt; char s[2505]; int hh[2][2505][2505],x[2]={29,31}; int nx[2505][2505]; ll dp[2505][2505]; map<ll,int> mp; int main(){ sf("%d",&n); sf(" %s",&s); sf("%d%d%d",&a,&b,&c); for(int z=0;z<2;++z){ for(int i=0;i<n;++i){ hh[z][i][i]=s[i]-'a'+1; for(int j=i+1;j<n;++j){ hh[z][i][j]=((ll)hh[z][i][j-1]*x[z]+s[j]-'a'+1)%mod; } } } for(int l=1;l<=n;++l){ mp.clear(); for(int i=n-1;i>=0;--i){ int j=i+l; if(j+l-1<=n-1){ int k=j+l-1; ll x=(ll)hh[0][j][k]*mod+hh[1][j][k]; mp[x]=j; } ll x=(ll)hh[0][i][i+l-1]*mod+hh[1][i][i+l-1]; if(mp.find(x)!=mp.end())nx[i][i+l-1]=mp[x]; else nx[i][i+l-1]=n; } } /* for(int i=0;i<n;++i){ for(int j=i;j<n;++j){ pf("nx "); for(int k=i;k<=j;++k)pf("%c",s[k]); pf(": %d\n",nx[i][j]); } } */ for(int i=n-1;i>=0;--i){ for(int j=i;j<n;++j){ dp[i][j]=dp[i+1][j]+a; } for(int j=i;j<n;++j){ int l=j-i+1; mnto(dp[i][j],dp[i][j-1]+a); int u=i,cnt=1; while(u!=n){ u=nx[u][u+l-1]; ++cnt; int tot=u+l-i; ll cost=dp[i][j]+b+(ll)cnt*c+(ll)(tot-cnt*l)*a; mnto(dp[i][u+l-1],cost); } } } pf("%lld\n",dp[0][n-1]); }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:67:8: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[2505]' [-Wformat=]
   67 |  sf(" %s",&s);
      |       ~^  ~~
      |        |  |
      |        |  char (*)[2505]
      |        char*
copypaste3.cpp:66:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  sf("%d",&n);
      |    ^
copypaste3.cpp:67:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  sf(" %s",&s);
      |    ^
copypaste3.cpp:68:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  sf("%d%d%d",&a,&b,&c);
      |    ^
#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...