oj.uz

Submission #567808

# Submission time Handle Problem Language Result Execution time Memory
567808 2022-05-24T08:34:31 Z jamezzz Copy and Paste 3 (JOI22_copypaste3) C++17
30 / 100
 3000 ms 2097152 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];
map<ii,int> mp;
vector<ii> v[2505*2505];
ll memo[2505][2505];
unordered_map<int,int> vis[2505][2505];

ll dp(int l,int r){
	if(l==r)return a;
	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=i;j<=r;++j){
			int x=hh[i][j];
			if(vis[l][r][x]!=0)continue;
			vis[l][r][x]=1;
			int far=l-1,cnt=0;
			for(ii pr:v[x]){
				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});
		}
	}
	
	memset(memo,-1,sizeof memo);
	pf("%lld\n",dp(0,n-1));
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 540524 KB Output is correct
2 Correct 275 ms 540568 KB Output is correct
3 Correct 301 ms 540616 KB Output is correct
4 Correct 280 ms 540720 KB Output is correct
5 Correct 263 ms 540684 KB Output is correct
6 Correct 258 ms 540608 KB Output is correct
7 Correct 262 ms 540788 KB Output is correct
8 Correct 255 ms 540520 KB Output is correct
9 Correct 281 ms 540636 KB Output is correct
10 Correct 257 ms 540736 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 540684 KB Output is correct
2 Correct 260 ms 540592 KB Output is correct
3 Correct 1288 ms 590396 KB Output is correct
4 Correct 1563 ms 597592 KB Output is correct
5 Correct 1865 ms 605856 KB Output is correct
6 Correct 2354 ms 616000 KB Output is correct
7 Correct 2836 ms 629128 KB Output is correct
8 Correct 2793 ms 629072 KB Output is correct
9 Correct 2822 ms 629144 KB Output is correct
10 Correct 273 ms 540584 KB Output is correct
11 Correct 285 ms 540616 KB Output is correct
12 Correct 262 ms 540620 KB Output is correct
13 Correct 257 ms 540528 KB Output is correct
14 Correct 259 ms 540580 KB Output is correct
15 Correct 266 ms 540668 KB Output is correct
16 Correct 268 ms 540748 KB Output is correct
17 Correct 274 ms 540524 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 540524 KB Output is correct
2 Correct 275 ms 540568 KB Output is correct
3 Correct 301 ms 540616 KB Output is correct
4 Correct 280 ms 540720 KB Output is correct
5 Correct 263 ms 540684 KB Output is correct
6 Correct 258 ms 540608 KB Output is correct
7 Correct 262 ms 540788 KB Output is correct
8 Correct 255 ms 540520 KB Output is correct
9 Correct 281 ms 540636 KB Output is correct
10 Correct 257 ms 540736 KB Output is correct
11 Correct 257 ms 540548 KB Output is correct
12 Correct 261 ms 540660 KB Output is correct
13 Correct 283 ms 540700 KB Output is correct
14 Correct 258 ms 540620 KB Output is correct
15 Correct 263 ms 540740 KB Output is correct
16 Correct 255 ms 540620 KB Output is correct
17 Correct 252 ms 540680 KB Output is correct
18 Correct 252 ms 540596 KB Output is correct
19 Correct 258 ms 540652 KB Output is correct
20 Correct 256 ms 540588 KB Output is correct
21 Correct 253 ms 540748 KB Output is correct
22 Correct 260 ms 540792 KB Output is correct
23 Correct 263 ms 540748 KB Output is correct
24 Correct 258 ms 540776 KB Output is correct
25 Correct 263 ms 540748 KB Output is correct
26 Correct 259 ms 540720 KB Output is correct
27 Correct 255 ms 540792 KB Output is correct
28 Correct 267 ms 540852 KB Output is correct
29 Correct 257 ms 540752 KB Output is correct
30 Correct 268 ms 540792 KB Output is correct
31 Correct 261 ms 540872 KB Output is correct
32 Correct 274 ms 540848 KB Output is correct
33 Correct 260 ms 540852 KB Output is correct
34 Correct 261 ms 540520 KB Output is correct
35 Correct 256 ms 540492 KB Output is correct
36 Correct 283 ms 540688 KB Output is correct
37 Correct 263 ms 540532 KB Output is correct
38 Correct 256 ms 540636 KB Output is correct
39 Correct 260 ms 540800 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 540524 KB Output is correct
2 Correct 275 ms 540568 KB Output is correct
3 Correct 301 ms 540616 KB Output is correct
4 Correct 280 ms 540720 KB Output is correct
5 Correct 263 ms 540684 KB Output is correct
6 Correct 258 ms 540608 KB Output is correct
7 Correct 262 ms 540788 KB Output is correct
8 Correct 255 ms 540520 KB Output is correct
9 Correct 281 ms 540636 KB Output is correct
10 Correct 257 ms 540736 KB Output is correct
11 Correct 257 ms 540548 KB Output is correct
12 Correct 261 ms 540660 KB Output is correct
13 Correct 283 ms 540700 KB Output is correct
14 Correct 258 ms 540620 KB Output is correct
15 Correct 263 ms 540740 KB Output is correct
16 Correct 255 ms 540620 KB Output is correct
17 Correct 252 ms 540680 KB Output is correct
18 Correct 252 ms 540596 KB Output is correct
19 Correct 258 ms 540652 KB Output is correct
20 Correct 256 ms 540588 KB Output is correct
21 Correct 253 ms 540748 KB Output is correct
22 Correct 260 ms 540792 KB Output is correct
23 Correct 263 ms 540748 KB Output is correct
24 Correct 258 ms 540776 KB Output is correct
25 Correct 263 ms 540748 KB Output is correct
26 Correct 259 ms 540720 KB Output is correct
27 Correct 255 ms 540792 KB Output is correct
28 Correct 267 ms 540852 KB Output is correct
29 Correct 257 ms 540752 KB Output is correct
30 Correct 268 ms 540792 KB Output is correct
31 Correct 261 ms 540872 KB Output is correct
32 Correct 274 ms 540848 KB Output is correct
33 Correct 260 ms 540852 KB Output is correct
34 Correct 261 ms 540520 KB Output is correct
35 Correct 256 ms 540492 KB Output is correct
36 Correct 283 ms 540688 KB Output is correct
37 Correct 263 ms 540532 KB Output is correct
38 Correct 256 ms 540636 KB Output is correct
39 Correct 260 ms 540800 KB Output is correct
40 Correct 271 ms 541460 KB Output is correct
41 Correct 270 ms 542028 KB Output is correct
42 Correct 268 ms 544204 KB Output is correct
43 Correct 268 ms 544076 KB Output is correct
44 Correct 280 ms 544200 KB Output is correct
45 Correct 267 ms 544076 KB Output is correct
46 Correct 267 ms 544088 KB Output is correct
47 Correct 443 ms 621432 KB Output is correct
48 Correct 645 ms 720644 KB Output is correct
49 Correct 507 ms 666128 KB Output is correct
50 Correct 518 ms 646372 KB Output is correct
51 Correct 557 ms 660184 KB Output is correct
52 Correct 571 ms 663176 KB Output is correct
53 Correct 272 ms 544152 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 540524 KB Output is correct
2 Correct 275 ms 540568 KB Output is correct
3 Correct 301 ms 540616 KB Output is correct
4 Correct 280 ms 540720 KB Output is correct
5 Correct 263 ms 540684 KB Output is correct
6 Correct 258 ms 540608 KB Output is correct
7 Correct 262 ms 540788 KB Output is correct
8 Correct 255 ms 540520 KB Output is correct
9 Correct 281 ms 540636 KB Output is correct
10 Correct 257 ms 540736 KB Output is correct
11 Correct 257 ms 540548 KB Output is correct
12 Correct 261 ms 540660 KB Output is correct
13 Correct 283 ms 540700 KB Output is correct
14 Correct 258 ms 540620 KB Output is correct
15 Correct 263 ms 540740 KB Output is correct
16 Correct 255 ms 540620 KB Output is correct
17 Correct 252 ms 540680 KB Output is correct
18 Correct 252 ms 540596 KB Output is correct
19 Correct 258 ms 540652 KB Output is correct
20 Correct 256 ms 540588 KB Output is correct
21 Correct 253 ms 540748 KB Output is correct
22 Correct 260 ms 540792 KB Output is correct
23 Correct 263 ms 540748 KB Output is correct
24 Correct 258 ms 540776 KB Output is correct
25 Correct 263 ms 540748 KB Output is correct
26 Correct 259 ms 540720 KB Output is correct
27 Correct 255 ms 540792 KB Output is correct
28 Correct 267 ms 540852 KB Output is correct
29 Correct 257 ms 540752 KB Output is correct
30 Correct 268 ms 540792 KB Output is correct
31 Correct 261 ms 540872 KB Output is correct
32 Correct 274 ms 540848 KB Output is correct
33 Correct 260 ms 540852 KB Output is correct
34 Correct 261 ms 540520 KB Output is correct
35 Correct 256 ms 540492 KB Output is correct
36 Correct 283 ms 540688 KB Output is correct
37 Correct 263 ms 540532 KB Output is correct
38 Correct 256 ms 540636 KB Output is correct
39 Correct 260 ms 540800 KB Output is correct
40 Correct 271 ms 541460 KB Output is correct
41 Correct 270 ms 542028 KB Output is correct
42 Correct 268 ms 544204 KB Output is correct
43 Correct 268 ms 544076 KB Output is correct
44 Correct 280 ms 544200 KB Output is correct
45 Correct 267 ms 544076 KB Output is correct
46 Correct 267 ms 544088 KB Output is correct
47 Correct 443 ms 621432 KB Output is correct
48 Correct 645 ms 720644 KB Output is correct
49 Correct 507 ms 666128 KB Output is correct
50 Correct 518 ms 646372 KB Output is correct
51 Correct 557 ms 660184 KB Output is correct
52 Correct 571 ms 663176 KB Output is correct
53 Correct 272 ms 544152 KB Output is correct
54 Correct 332 ms 557184 KB Output is correct
55 Correct 476 ms 557516 KB Output is correct
56 Correct 839 ms 615800 KB Output is correct
57 Correct 850 ms 614832 KB Output is correct
58 Correct 826 ms 614700 KB Output is correct
59 Correct 821 ms 614716 KB Output is correct
60 Correct 827 ms 614676 KB Output is correct
61 Execution timed out 3002 ms 2097152 KB Time limit exceeded
62 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 540524 KB Output is correct
2 Correct 275 ms 540568 KB Output is correct
3 Correct 301 ms 540616 KB Output is correct
4 Correct 280 ms 540720 KB Output is correct
5 Correct 263 ms 540684 KB Output is correct
6 Correct 258 ms 540608 KB Output is correct
7 Correct 262 ms 540788 KB Output is correct
8 Correct 255 ms 540520 KB Output is correct
9 Correct 281 ms 540636 KB Output is correct
10 Correct 257 ms 540736 KB Output is correct
11 Correct 269 ms 540684 KB Output is correct
12 Correct 260 ms 540592 KB Output is correct
13 Correct 1288 ms 590396 KB Output is correct
14 Correct 1563 ms 597592 KB Output is correct
15 Correct 1865 ms 605856 KB Output is correct
16 Correct 2354 ms 616000 KB Output is correct
17 Correct 2836 ms 629128 KB Output is correct
18 Correct 2793 ms 629072 KB Output is correct
19 Correct 2822 ms 629144 KB Output is correct
20 Correct 273 ms 540584 KB Output is correct
21 Correct 285 ms 540616 KB Output is correct
22 Correct 262 ms 540620 KB Output is correct
23 Correct 257 ms 540528 KB Output is correct
24 Correct 259 ms 540580 KB Output is correct
25 Correct 266 ms 540668 KB Output is correct
26 Correct 268 ms 540748 KB Output is correct
27 Correct 274 ms 540524 KB Output is correct
28 Correct 257 ms 540548 KB Output is correct
29 Correct 261 ms 540660 KB Output is correct
30 Correct 283 ms 540700 KB Output is correct
31 Correct 258 ms 540620 KB Output is correct
32 Correct 263 ms 540740 KB Output is correct
33 Correct 255 ms 540620 KB Output is correct
34 Correct 252 ms 540680 KB Output is correct
35 Correct 252 ms 540596 KB Output is correct
36 Correct 258 ms 540652 KB Output is correct
37 Correct 256 ms 540588 KB Output is correct
38 Correct 253 ms 540748 KB Output is correct
39 Correct 260 ms 540792 KB Output is correct
40 Correct 263 ms 540748 KB Output is correct
41 Correct 258 ms 540776 KB Output is correct
42 Correct 263 ms 540748 KB Output is correct
43 Correct 259 ms 540720 KB Output is correct
44 Correct 255 ms 540792 KB Output is correct
45 Correct 267 ms 540852 KB Output is correct
46 Correct 257 ms 540752 KB Output is correct
47 Correct 268 ms 540792 KB Output is correct
48 Correct 261 ms 540872 KB Output is correct
49 Correct 274 ms 540848 KB Output is correct
50 Correct 260 ms 540852 KB Output is correct
51 Correct 261 ms 540520 KB Output is correct
52 Correct 256 ms 540492 KB Output is correct
53 Correct 283 ms 540688 KB Output is correct
54 Correct 263 ms 540532 KB Output is correct
55 Correct 256 ms 540636 KB Output is correct
56 Correct 260 ms 540800 KB Output is correct
57 Correct 271 ms 541460 KB Output is correct
58 Correct 270 ms 542028 KB Output is correct
59 Correct 268 ms 544204 KB Output is correct
60 Correct 268 ms 544076 KB Output is correct
61 Correct 280 ms 544200 KB Output is correct
62 Correct 267 ms 544076 KB Output is correct
63 Correct 267 ms 544088 KB Output is correct
64 Correct 443 ms 621432 KB Output is correct
65 Correct 645 ms 720644 KB Output is correct
66 Correct 507 ms 666128 KB Output is correct
67 Correct 518 ms 646372 KB Output is correct
68 Correct 557 ms 660184 KB Output is correct
69 Correct 571 ms 663176 KB Output is correct
70 Correct 272 ms 544152 KB Output is correct
71 Correct 332 ms 557184 KB Output is correct
72 Correct 476 ms 557516 KB Output is correct
73 Correct 839 ms 615800 KB Output is correct
74 Correct 850 ms 614832 KB Output is correct
75 Correct 826 ms 614700 KB Output is correct
76 Correct 821 ms 614716 KB Output is correct
77 Correct 827 ms 614676 KB Output is correct
78 Execution timed out 3002 ms 2097152 KB Time limit exceeded
79 Halted 0 ms 0 KB -