oj.uz

답안 #567845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567845 2022-05-24T09:18:41 Z jamezzz Copy and Paste 3 (JOI22_copypaste3) C++17
1 / 100
 1759 ms 629344 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/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

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 540640 KB Output is correct
2 Correct 257 ms 540620 KB Output is correct
3 Correct 259 ms 540760 KB Output is correct
4 Correct 257 ms 540652 KB Output is correct
5 Correct 268 ms 540692 KB Output is correct
6 Correct 263 ms 540688 KB Output is correct
7 Correct 257 ms 540672 KB Output is correct
8 Correct 266 ms 540676 KB Output is correct
9 Correct 263 ms 540644 KB Output is correct
10 Correct 258 ms 540656 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 540744 KB Output is correct
2 Correct 277 ms 540688 KB Output is correct
3 Correct 856 ms 590660 KB Output is correct
4 Correct 993 ms 597504 KB Output is correct
5 Correct 1174 ms 605836 KB Output is correct
6 Correct 1403 ms 616276 KB Output is correct
7 Correct 1692 ms 629288 KB Output is correct
8 Incorrect 1759 ms 629344 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 540640 KB Output is correct
2 Correct 257 ms 540620 KB Output is correct
3 Correct 259 ms 540760 KB Output is correct
4 Correct 257 ms 540652 KB Output is correct
5 Correct 268 ms 540692 KB Output is correct
6 Correct 263 ms 540688 KB Output is correct
7 Correct 257 ms 540672 KB Output is correct
8 Correct 266 ms 540676 KB Output is correct
9 Correct 263 ms 540644 KB Output is correct
10 Correct 258 ms 540656 KB Output is correct
11 Correct 282 ms 540824 KB Output is correct
12 Correct 268 ms 540656 KB Output is correct
13 Correct 287 ms 540696 KB Output is correct
14 Correct 266 ms 540768 KB Output is correct
15 Correct 265 ms 540648 KB Output is correct
16 Correct 261 ms 540692 KB Output is correct
17 Correct 266 ms 540684 KB Output is correct
18 Correct 281 ms 540700 KB Output is correct
19 Correct 292 ms 540716 KB Output is correct
20 Correct 264 ms 540736 KB Output is correct
21 Correct 264 ms 540908 KB Output is correct
22 Correct 271 ms 540852 KB Output is correct
23 Correct 284 ms 540748 KB Output is correct
24 Correct 270 ms 540848 KB Output is correct
25 Correct 274 ms 540844 KB Output is correct
26 Correct 277 ms 540768 KB Output is correct
27 Correct 278 ms 540848 KB Output is correct
28 Correct 306 ms 540836 KB Output is correct
29 Correct 303 ms 540844 KB Output is correct
30 Correct 331 ms 540836 KB Output is correct
31 Correct 297 ms 540856 KB Output is correct
32 Correct 281 ms 540860 KB Output is correct
33 Correct 276 ms 540844 KB Output is correct
34 Correct 297 ms 540636 KB Output is correct
35 Correct 276 ms 540688 KB Output is correct
36 Correct 297 ms 540828 KB Output is correct
37 Correct 279 ms 540712 KB Output is correct
38 Correct 305 ms 540636 KB Output is correct
39 Incorrect 292 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 540640 KB Output is correct
2 Correct 257 ms 540620 KB Output is correct
3 Correct 259 ms 540760 KB Output is correct
4 Correct 257 ms 540652 KB Output is correct
5 Correct 268 ms 540692 KB Output is correct
6 Correct 263 ms 540688 KB Output is correct
7 Correct 257 ms 540672 KB Output is correct
8 Correct 266 ms 540676 KB Output is correct
9 Correct 263 ms 540644 KB Output is correct
10 Correct 258 ms 540656 KB Output is correct
11 Correct 282 ms 540824 KB Output is correct
12 Correct 268 ms 540656 KB Output is correct
13 Correct 287 ms 540696 KB Output is correct
14 Correct 266 ms 540768 KB Output is correct
15 Correct 265 ms 540648 KB Output is correct
16 Correct 261 ms 540692 KB Output is correct
17 Correct 266 ms 540684 KB Output is correct
18 Correct 281 ms 540700 KB Output is correct
19 Correct 292 ms 540716 KB Output is correct
20 Correct 264 ms 540736 KB Output is correct
21 Correct 264 ms 540908 KB Output is correct
22 Correct 271 ms 540852 KB Output is correct
23 Correct 284 ms 540748 KB Output is correct
24 Correct 270 ms 540848 KB Output is correct
25 Correct 274 ms 540844 KB Output is correct
26 Correct 277 ms 540768 KB Output is correct
27 Correct 278 ms 540848 KB Output is correct
28 Correct 306 ms 540836 KB Output is correct
29 Correct 303 ms 540844 KB Output is correct
30 Correct 331 ms 540836 KB Output is correct
31 Correct 297 ms 540856 KB Output is correct
32 Correct 281 ms 540860 KB Output is correct
33 Correct 276 ms 540844 KB Output is correct
34 Correct 297 ms 540636 KB Output is correct
35 Correct 276 ms 540688 KB Output is correct
36 Correct 297 ms 540828 KB Output is correct
37 Correct 279 ms 540712 KB Output is correct
38 Correct 305 ms 540636 KB Output is correct
39 Incorrect 292 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 540640 KB Output is correct
2 Correct 257 ms 540620 KB Output is correct
3 Correct 259 ms 540760 KB Output is correct
4 Correct 257 ms 540652 KB Output is correct
5 Correct 268 ms 540692 KB Output is correct
6 Correct 263 ms 540688 KB Output is correct
7 Correct 257 ms 540672 KB Output is correct
8 Correct 266 ms 540676 KB Output is correct
9 Correct 263 ms 540644 KB Output is correct
10 Correct 258 ms 540656 KB Output is correct
11 Correct 282 ms 540824 KB Output is correct
12 Correct 268 ms 540656 KB Output is correct
13 Correct 287 ms 540696 KB Output is correct
14 Correct 266 ms 540768 KB Output is correct
15 Correct 265 ms 540648 KB Output is correct
16 Correct 261 ms 540692 KB Output is correct
17 Correct 266 ms 540684 KB Output is correct
18 Correct 281 ms 540700 KB Output is correct
19 Correct 292 ms 540716 KB Output is correct
20 Correct 264 ms 540736 KB Output is correct
21 Correct 264 ms 540908 KB Output is correct
22 Correct 271 ms 540852 KB Output is correct
23 Correct 284 ms 540748 KB Output is correct
24 Correct 270 ms 540848 KB Output is correct
25 Correct 274 ms 540844 KB Output is correct
26 Correct 277 ms 540768 KB Output is correct
27 Correct 278 ms 540848 KB Output is correct
28 Correct 306 ms 540836 KB Output is correct
29 Correct 303 ms 540844 KB Output is correct
30 Correct 331 ms 540836 KB Output is correct
31 Correct 297 ms 540856 KB Output is correct
32 Correct 281 ms 540860 KB Output is correct
33 Correct 276 ms 540844 KB Output is correct
34 Correct 297 ms 540636 KB Output is correct
35 Correct 276 ms 540688 KB Output is correct
36 Correct 297 ms 540828 KB Output is correct
37 Correct 279 ms 540712 KB Output is correct
38 Correct 305 ms 540636 KB Output is correct
39 Incorrect 292 ms 540812 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 540640 KB Output is correct
2 Correct 257 ms 540620 KB Output is correct
3 Correct 259 ms 540760 KB Output is correct
4 Correct 257 ms 540652 KB Output is correct
5 Correct 268 ms 540692 KB Output is correct
6 Correct 263 ms 540688 KB Output is correct
7 Correct 257 ms 540672 KB Output is correct
8 Correct 266 ms 540676 KB Output is correct
9 Correct 263 ms 540644 KB Output is correct
10 Correct 258 ms 540656 KB Output is correct
11 Correct 273 ms 540744 KB Output is correct
12 Correct 277 ms 540688 KB Output is correct
13 Correct 856 ms 590660 KB Output is correct
14 Correct 993 ms 597504 KB Output is correct
15 Correct 1174 ms 605836 KB Output is correct
16 Correct 1403 ms 616276 KB Output is correct
17 Correct 1692 ms 629288 KB Output is correct
18 Incorrect 1759 ms 629344 KB Output isn't correct
19 Halted 0 ms 0 KB -