oj.uz

Submission #567857

# Submission time Handle Problem Language Result Execution time Memory
567857 2022-05-24T09:31:24 Z jamezzz Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1764 ms 629196 KB 
#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[2505][2505],num[2505*2505];
map<ii,int> mp;
vector<ii> v[2505*2505];
vector<int> pos[2505];
ll memo[2505][2505];
unordered_map<int,int> vis[2505][2505];

ll dp(int l,int r){
	if(l==r)return a;
	if(l+1==r){
		if(s[l]!=s[r])return 2*a;
		return min(2*a,a+b+2*c);
	}
	if(memo[l][r]!=-1)return memo[l][r];
	ll ans=(ll)(r-l+1)*a;
	for(int i=l;i<=r;++i){
		for(int j:pos[i]){
			if(j>(r+l)/2+1)break;
			int x=hh[i][j];
			if(vis[l][r][x]!=0)continue;
			vis[l][r][x]=1;
			int far=l-1,cnt=0;
			for(int i=lower_bound(all(v[x]),ii(l,l))-v[x].begin();i<sz(v[x]);++i){
				ii pr=v[x][i];
				if(pr.se>r)break;
				if(far<pr.fi&&pr.se<=r){
					++cnt;
					far=pr.se;
				}
			}
			if(cnt==1)continue;
			ans=min(ans,dp(v[x][0].fi,v[x][0].se)+b+(ll)cnt*c+(ll)(r-l+1-cnt*(j-i+1))*a);
		}
	}
	return memo[l][r]=ans;
}

int main(){
	sf("%d",&n);
	sf(" %s",&s);
	sf("%d%d%d",&a,&b,&c);
	for(int i=0;i<n;++i){
		ll cur=0,cur2=0;
		ll pw=1,pw2=1;
		for(int j=i;j<n;++j){
			cur+=pw*(s[j]-'a'+1);
			cur2+=pw2*(s[j]-'a'+1);
			cur%=mod;
			cur2%=mod2;
			pw*=31;pw%=mod;
			pw2*=31;pw2%=mod2;
			ii pr=ii((int)cur,(int)cur2);
			if(!mp.count(pr)){
				mp[pr]=cnt++;
			}
			hh[i][j]=mp[pr];
			v[hh[i][j]].pb({i,j});
		}
	}
	
	for(int i=n-1;i>=0;--i){
		for(int j=i;j<n;++j){
			if(num[hh[i][j]]!=0)pos[i].pb(j);
			++num[hh[i][j]];
		}
	}
	
	memset(memo,-1,sizeof memo);
	pf("%lld\n",dp(0,n-1));
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 540692 KB Output is correct
2 Correct 271 ms 540696 KB Output is correct
3 Correct 260 ms 540688 KB Output is correct
4 Correct 289 ms 540636 KB Output is correct
5 Correct 291 ms 540696 KB Output is correct
6 Correct 282 ms 540592 KB Output is correct
7 Correct 263 ms 540596 KB Output is correct
8 Correct 279 ms 540704 KB Output is correct
9 Correct 292 ms 540580 KB Output is correct
10 Correct 270 ms 540656 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 540936 KB Output is correct
2 Correct 300 ms 540732 KB Output is correct
3 Correct 870 ms 590584 KB Output is correct
4 Correct 993 ms 597464 KB Output is correct
5 Correct 1353 ms 606012 KB Output is correct
6 Correct 1387 ms 616256 KB Output is correct
7 Correct 1764 ms 629196 KB Output is correct
8 Incorrect 1712 ms 629180 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 540692 KB Output is correct
2 Correct 271 ms 540696 KB Output is correct
3 Correct 260 ms 540688 KB Output is correct
4 Correct 289 ms 540636 KB Output is correct
5 Correct 291 ms 540696 KB Output is correct
6 Correct 282 ms 540592 KB Output is correct
7 Correct 263 ms 540596 KB Output is correct
8 Correct 279 ms 540704 KB Output is correct
9 Correct 292 ms 540580 KB Output is correct
10 Correct 270 ms 540656 KB Output is correct
11 Correct 268 ms 540736 KB Output is correct
12 Correct 275 ms 540740 KB Output is correct
13 Correct 269 ms 540700 KB Output is correct
14 Correct 269 ms 540596 KB Output is correct
15 Correct 287 ms 540772 KB Output is correct
16 Correct 275 ms 540668 KB Output is correct
17 Correct 279 ms 540620 KB Output is correct
18 Correct 258 ms 540788 KB Output is correct
19 Correct 304 ms 540820 KB Output is correct
20 Correct 301 ms 540784 KB Output is correct
21 Correct 309 ms 540876 KB Output is correct
22 Correct 261 ms 540848 KB Output is correct
23 Correct 276 ms 540844 KB Output is correct
24 Correct 272 ms 540844 KB Output is correct
25 Correct 261 ms 540812 KB Output is correct
26 Correct 273 ms 540828 KB Output is correct
27 Correct 278 ms 540852 KB Output is correct
28 Correct 298 ms 540760 KB Output is correct
29 Correct 270 ms 540848 KB Output is correct
30 Correct 260 ms 540912 KB Output is correct
31 Correct 269 ms 540880 KB Output is correct
32 Correct 269 ms 540780 KB Output is correct
33 Correct 267 ms 540780 KB Output is correct
34 Correct 274 ms 540692 KB Output is correct
35 Correct 286 ms 540748 KB Output is correct
36 Correct 255 ms 540592 KB Output is correct
37 Correct 302 ms 540656 KB Output is correct
38 Correct 281 ms 540708 KB Output is correct
39 Incorrect 264 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 540692 KB Output is correct
2 Correct 271 ms 540696 KB Output is correct
3 Correct 260 ms 540688 KB Output is correct
4 Correct 289 ms 540636 KB Output is correct
5 Correct 291 ms 540696 KB Output is correct
6 Correct 282 ms 540592 KB Output is correct
7 Correct 263 ms 540596 KB Output is correct
8 Correct 279 ms 540704 KB Output is correct
9 Correct 292 ms 540580 KB Output is correct
10 Correct 270 ms 540656 KB Output is correct
11 Correct 268 ms 540736 KB Output is correct
12 Correct 275 ms 540740 KB Output is correct
13 Correct 269 ms 540700 KB Output is correct
14 Correct 269 ms 540596 KB Output is correct
15 Correct 287 ms 540772 KB Output is correct
16 Correct 275 ms 540668 KB Output is correct
17 Correct 279 ms 540620 KB Output is correct
18 Correct 258 ms 540788 KB Output is correct
19 Correct 304 ms 540820 KB Output is correct
20 Correct 301 ms 540784 KB Output is correct
21 Correct 309 ms 540876 KB Output is correct
22 Correct 261 ms 540848 KB Output is correct
23 Correct 276 ms 540844 KB Output is correct
24 Correct 272 ms 540844 KB Output is correct
25 Correct 261 ms 540812 KB Output is correct
26 Correct 273 ms 540828 KB Output is correct
27 Correct 278 ms 540852 KB Output is correct
28 Correct 298 ms 540760 KB Output is correct
29 Correct 270 ms 540848 KB Output is correct
30 Correct 260 ms 540912 KB Output is correct
31 Correct 269 ms 540880 KB Output is correct
32 Correct 269 ms 540780 KB Output is correct
33 Correct 267 ms 540780 KB Output is correct
34 Correct 274 ms 540692 KB Output is correct
35 Correct 286 ms 540748 KB Output is correct
36 Correct 255 ms 540592 KB Output is correct
37 Correct 302 ms 540656 KB Output is correct
38 Correct 281 ms 540708 KB Output is correct
39 Incorrect 264 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 540692 KB Output is correct
2 Correct 271 ms 540696 KB Output is correct
3 Correct 260 ms 540688 KB Output is correct
4 Correct 289 ms 540636 KB Output is correct
5 Correct 291 ms 540696 KB Output is correct
6 Correct 282 ms 540592 KB Output is correct
7 Correct 263 ms 540596 KB Output is correct
8 Correct 279 ms 540704 KB Output is correct
9 Correct 292 ms 540580 KB Output is correct
10 Correct 270 ms 540656 KB Output is correct
11 Correct 268 ms 540736 KB Output is correct
12 Correct 275 ms 540740 KB Output is correct
13 Correct 269 ms 540700 KB Output is correct
14 Correct 269 ms 540596 KB Output is correct
15 Correct 287 ms 540772 KB Output is correct
16 Correct 275 ms 540668 KB Output is correct
17 Correct 279 ms 540620 KB Output is correct
18 Correct 258 ms 540788 KB Output is correct
19 Correct 304 ms 540820 KB Output is correct
20 Correct 301 ms 540784 KB Output is correct
21 Correct 309 ms 540876 KB Output is correct
22 Correct 261 ms 540848 KB Output is correct
23 Correct 276 ms 540844 KB Output is correct
24 Correct 272 ms 540844 KB Output is correct
25 Correct 261 ms 540812 KB Output is correct
26 Correct 273 ms 540828 KB Output is correct
27 Correct 278 ms 540852 KB Output is correct
28 Correct 298 ms 540760 KB Output is correct
29 Correct 270 ms 540848 KB Output is correct
30 Correct 260 ms 540912 KB Output is correct
31 Correct 269 ms 540880 KB Output is correct
32 Correct 269 ms 540780 KB Output is correct
33 Correct 267 ms 540780 KB Output is correct
34 Correct 274 ms 540692 KB Output is correct
35 Correct 286 ms 540748 KB Output is correct
36 Correct 255 ms 540592 KB Output is correct
37 Correct 302 ms 540656 KB Output is correct
38 Correct 281 ms 540708 KB Output is correct
39 Incorrect 264 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 540692 KB Output is correct
2 Correct 271 ms 540696 KB Output is correct
3 Correct 260 ms 540688 KB Output is correct
4 Correct 289 ms 540636 KB Output is correct
5 Correct 291 ms 540696 KB Output is correct
6 Correct 282 ms 540592 KB Output is correct
7 Correct 263 ms 540596 KB Output is correct
8 Correct 279 ms 540704 KB Output is correct
9 Correct 292 ms 540580 KB Output is correct
10 Correct 270 ms 540656 KB Output is correct
11 Correct 298 ms 540936 KB Output is correct
12 Correct 300 ms 540732 KB Output is correct
13 Correct 870 ms 590584 KB Output is correct
14 Correct 993 ms 597464 KB Output is correct
15 Correct 1353 ms 606012 KB Output is correct
16 Correct 1387 ms 616256 KB Output is correct
17 Correct 1764 ms 629196 KB Output is correct
18 Incorrect 1712 ms 629180 KB Output isn't correct
19 Halted 0 ms 0 KB -