oj.uz

Submission #567844

# Submission time Handle Problem Language Result Execution time Memory
567844 2022-05-24T09:18:00 Z jamezzz Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1841 ms 629224 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+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/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 281 ms 540656 KB Output is correct
2 Correct 254 ms 540604 KB Output is correct
3 Correct 263 ms 540696 KB Output is correct
4 Correct 301 ms 540672 KB Output is correct
5 Correct 266 ms 540676 KB Output is correct
6 Correct 259 ms 540680 KB Output is correct
7 Correct 280 ms 540620 KB Output is correct
8 Correct 266 ms 540736 KB Output is correct
9 Correct 271 ms 540688 KB Output is correct
10 Correct 261 ms 540588 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 540744 KB Output is correct
2 Correct 268 ms 540596 KB Output is correct
3 Correct 863 ms 590676 KB Output is correct
4 Correct 973 ms 597396 KB Output is correct
5 Correct 1198 ms 605980 KB Output is correct
6 Correct 1373 ms 616108 KB Output is correct
7 Correct 1841 ms 629224 KB Output is correct
8 Incorrect 1790 ms 629192 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 540656 KB Output is correct
2 Correct 254 ms 540604 KB Output is correct
3 Correct 263 ms 540696 KB Output is correct
4 Correct 301 ms 540672 KB Output is correct
5 Correct 266 ms 540676 KB Output is correct
6 Correct 259 ms 540680 KB Output is correct
7 Correct 280 ms 540620 KB Output is correct
8 Correct 266 ms 540736 KB Output is correct
9 Correct 271 ms 540688 KB Output is correct
10 Correct 261 ms 540588 KB Output is correct
11 Correct 264 ms 540732 KB Output is correct
12 Correct 274 ms 540692 KB Output is correct
13 Correct 259 ms 540704 KB Output is correct
14 Correct 277 ms 540848 KB Output is correct
15 Correct 278 ms 540772 KB Output is correct
16 Correct 292 ms 540736 KB Output is correct
17 Correct 265 ms 540676 KB Output is correct
18 Correct 274 ms 540664 KB Output is correct
19 Correct 265 ms 540744 KB Output is correct
20 Correct 270 ms 540700 KB Output is correct
21 Correct 271 ms 540788 KB Output is correct
22 Correct 257 ms 540756 KB Output is correct
23 Correct 267 ms 540836 KB Output is correct
24 Correct 267 ms 540912 KB Output is correct
25 Correct 264 ms 540840 KB Output is correct
26 Correct 295 ms 540748 KB Output is correct
27 Correct 270 ms 540832 KB Output is correct
28 Correct 259 ms 540908 KB Output is correct
29 Correct 303 ms 540848 KB Output is correct
30 Correct 261 ms 540752 KB Output is correct
31 Correct 269 ms 540748 KB Output is correct
32 Correct 273 ms 540800 KB Output is correct
33 Correct 260 ms 540876 KB Output is correct
34 Correct 257 ms 540584 KB Output is correct
35 Correct 271 ms 540712 KB Output is correct
36 Correct 280 ms 540780 KB Output is correct
37 Correct 259 ms 540712 KB Output is correct
38 Correct 271 ms 540708 KB Output is correct
39 Incorrect 283 ms 540700 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 540656 KB Output is correct
2 Correct 254 ms 540604 KB Output is correct
3 Correct 263 ms 540696 KB Output is correct
4 Correct 301 ms 540672 KB Output is correct
5 Correct 266 ms 540676 KB Output is correct
6 Correct 259 ms 540680 KB Output is correct
7 Correct 280 ms 540620 KB Output is correct
8 Correct 266 ms 540736 KB Output is correct
9 Correct 271 ms 540688 KB Output is correct
10 Correct 261 ms 540588 KB Output is correct
11 Correct 264 ms 540732 KB Output is correct
12 Correct 274 ms 540692 KB Output is correct
13 Correct 259 ms 540704 KB Output is correct
14 Correct 277 ms 540848 KB Output is correct
15 Correct 278 ms 540772 KB Output is correct
16 Correct 292 ms 540736 KB Output is correct
17 Correct 265 ms 540676 KB Output is correct
18 Correct 274 ms 540664 KB Output is correct
19 Correct 265 ms 540744 KB Output is correct
20 Correct 270 ms 540700 KB Output is correct
21 Correct 271 ms 540788 KB Output is correct
22 Correct 257 ms 540756 KB Output is correct
23 Correct 267 ms 540836 KB Output is correct
24 Correct 267 ms 540912 KB Output is correct
25 Correct 264 ms 540840 KB Output is correct
26 Correct 295 ms 540748 KB Output is correct
27 Correct 270 ms 540832 KB Output is correct
28 Correct 259 ms 540908 KB Output is correct
29 Correct 303 ms 540848 KB Output is correct
30 Correct 261 ms 540752 KB Output is correct
31 Correct 269 ms 540748 KB Output is correct
32 Correct 273 ms 540800 KB Output is correct
33 Correct 260 ms 540876 KB Output is correct
34 Correct 257 ms 540584 KB Output is correct
35 Correct 271 ms 540712 KB Output is correct
36 Correct 280 ms 540780 KB Output is correct
37 Correct 259 ms 540712 KB Output is correct
38 Correct 271 ms 540708 KB Output is correct
39 Incorrect 283 ms 540700 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 540656 KB Output is correct
2 Correct 254 ms 540604 KB Output is correct
3 Correct 263 ms 540696 KB Output is correct
4 Correct 301 ms 540672 KB Output is correct
5 Correct 266 ms 540676 KB Output is correct
6 Correct 259 ms 540680 KB Output is correct
7 Correct 280 ms 540620 KB Output is correct
8 Correct 266 ms 540736 KB Output is correct
9 Correct 271 ms 540688 KB Output is correct
10 Correct 261 ms 540588 KB Output is correct
11 Correct 264 ms 540732 KB Output is correct
12 Correct 274 ms 540692 KB Output is correct
13 Correct 259 ms 540704 KB Output is correct
14 Correct 277 ms 540848 KB Output is correct
15 Correct 278 ms 540772 KB Output is correct
16 Correct 292 ms 540736 KB Output is correct
17 Correct 265 ms 540676 KB Output is correct
18 Correct 274 ms 540664 KB Output is correct
19 Correct 265 ms 540744 KB Output is correct
20 Correct 270 ms 540700 KB Output is correct
21 Correct 271 ms 540788 KB Output is correct
22 Correct 257 ms 540756 KB Output is correct
23 Correct 267 ms 540836 KB Output is correct
24 Correct 267 ms 540912 KB Output is correct
25 Correct 264 ms 540840 KB Output is correct
26 Correct 295 ms 540748 KB Output is correct
27 Correct 270 ms 540832 KB Output is correct
28 Correct 259 ms 540908 KB Output is correct
29 Correct 303 ms 540848 KB Output is correct
30 Correct 261 ms 540752 KB Output is correct
31 Correct 269 ms 540748 KB Output is correct
32 Correct 273 ms 540800 KB Output is correct
33 Correct 260 ms 540876 KB Output is correct
34 Correct 257 ms 540584 KB Output is correct
35 Correct 271 ms 540712 KB Output is correct
36 Correct 280 ms 540780 KB Output is correct
37 Correct 259 ms 540712 KB Output is correct
38 Correct 271 ms 540708 KB Output is correct
39 Incorrect 283 ms 540700 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 540656 KB Output is correct
2 Correct 254 ms 540604 KB Output is correct
3 Correct 263 ms 540696 KB Output is correct
4 Correct 301 ms 540672 KB Output is correct
5 Correct 266 ms 540676 KB Output is correct
6 Correct 259 ms 540680 KB Output is correct
7 Correct 280 ms 540620 KB Output is correct
8 Correct 266 ms 540736 KB Output is correct
9 Correct 271 ms 540688 KB Output is correct
10 Correct 261 ms 540588 KB Output is correct
11 Correct 271 ms 540744 KB Output is correct
12 Correct 268 ms 540596 KB Output is correct
13 Correct 863 ms 590676 KB Output is correct
14 Correct 973 ms 597396 KB Output is correct
15 Correct 1198 ms 605980 KB Output is correct
16 Correct 1373 ms 616108 KB Output is correct
17 Correct 1841 ms 629224 KB Output is correct
18 Incorrect 1790 ms 629192 KB Output isn't correct
19 Halted 0 ms 0 KB -