답안 #833637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833637	2023-08-22T07:18:28 Z	CSQ31	Chorus (JOI23_chorus)	C++17	40 / 100	139 ms	86812 KB

chorus

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 1e6+5;
int a[MAXN],n,k;
ll dp[2222][2222],p[MAXN];
int main()
{
	string s;
	cin>>n>>k>>s;
	int cur = 0,nxt = 0;
	for(int i=0;i<2*n;i++){
		if(s[i] == 'A')cur++;
		else a[++nxt] = cur;
	}
	for(int i=1;i<=n;i++)p[i] = p[i-1]+a[i];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=k;j++){
			dp[i][j] = 1e9;	
		}
	} 
	dp[0][0] = 0;
	for(int x=1;x<=k;x++){
		int l = 0;
		for(int i=1;i<=n;i++){
			while(l+1<=i && a[l+1] <= i)l++;
			for(int j=l;j>=0;j--){
				dp[i][x] = min(dp[i][x],i*l - p[l] - (i*j - dp[j][x-1] - p[j]));
			}
			
		}
		
	}
	cout<<dp[n][k];
}

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	22 ms	2644 KB	Output is correct
19	Correct	69 ms	3412 KB	Output is correct
20	Correct	2 ms	2260 KB	Output is correct
21	Correct	2 ms	2260 KB	Output is correct
22	Correct	139 ms	4304 KB	Output is correct
23	Correct	125 ms	4300 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	113 ms	4296 KB	Output is correct
26	Correct	108 ms	3968 KB	Output is correct
27	Correct	40 ms	2976 KB	Output is correct
28	Correct	37 ms	2900 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	22 ms	2644 KB	Output is correct
19	Correct	69 ms	3412 KB	Output is correct
20	Correct	2 ms	2260 KB	Output is correct
21	Correct	2 ms	2260 KB	Output is correct
22	Correct	139 ms	4304 KB	Output is correct
23	Correct	125 ms	4300 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	113 ms	4296 KB	Output is correct
26	Correct	108 ms	3968 KB	Output is correct
27	Correct	40 ms	2976 KB	Output is correct
28	Correct	37 ms	2900 KB	Output is correct
29	Runtime error	66 ms	86812 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	22 ms	2644 KB	Output is correct
19	Correct	69 ms	3412 KB	Output is correct
20	Correct	2 ms	2260 KB	Output is correct
21	Correct	2 ms	2260 KB	Output is correct
22	Correct	139 ms	4304 KB	Output is correct
23	Correct	125 ms	4300 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	113 ms	4296 KB	Output is correct
26	Correct	108 ms	3968 KB	Output is correct
27	Correct	40 ms	2976 KB	Output is correct
28	Correct	37 ms	2900 KB	Output is correct
29	Runtime error	66 ms	86812 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	2 ms	1108 KB	Output is correct
18	Correct	22 ms	2644 KB	Output is correct
19	Correct	69 ms	3412 KB	Output is correct
20	Correct	2 ms	2260 KB	Output is correct
21	Correct	2 ms	2260 KB	Output is correct
22	Correct	139 ms	4304 KB	Output is correct
23	Correct	125 ms	4300 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	113 ms	4296 KB	Output is correct
26	Correct	108 ms	3968 KB	Output is correct
27	Correct	40 ms	2976 KB	Output is correct
28	Correct	37 ms	2900 KB	Output is correct
29	Runtime error	66 ms	86812 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

답안 #833637

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0