Submission #776300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776300	2023-07-07T15:36:10 Z	Arturgo	Chorus (JOI23_chorus)	C++14	61 / 100	7000 ms	4388 KB

chorus

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int DEC = 1e12;

const int INFINI = 1e18;

int N, K;
string types;

vector<int> ouvrantes, fermantes;
vector<int> derFermantes, cumOuvrAvant;

// bornes incluses
int cout_transition(int i, int j) {
	int df = derFermantes[j];
	
	if(df < i) return 0;
	
	int deb = i;
	int fin = min(j, df);
	
	return (j + 1) * (fin - deb + 1)
	- (cumOuvrAvant[fin + 1] - cumOuvrAvant[deb]);
}

pair<int, int> calc(int coutGroupe) {
	vector<pair<int, int>> dyns;
	
	dyns.push_back({0, 0});
	for(int pos = 0;pos < N;pos++) {
		pair<int, int> mini = {INFINI, 0};
		
		for(int deb = 0;deb <= pos;deb++) {
			mini = min(mini, {
				cout_transition(deb, pos)
				+ dyns[deb].first
				+ coutGroupe, 
				dyns[deb].second + 1
			});
		}
		
		dyns.push_back(mini);
	}
	
	return dyns.back();
}

signed main() {
	cin >> N >> K;
	cin >> types;
	
	cumOuvrAvant.push_back(0);
	
	for(int i = 0;i < 2 * N;i++) {
		if(types[i] == 'A') {
			ouvrantes.push_back(i);
			derFermantes.push_back((int)fermantes.size() - 1);
		}
		else {
			fermantes.push_back(i);
			cumOuvrAvant.push_back(
				cumOuvrAvant.back()
				+ (int)ouvrantes.size()			
			);
		}
	}
	
	int deb = -1000ll * 1000 * 1000 * 1000ll, fin = 1000ll * 1000 * 1000 * 1000ll;
	
	while(fin - deb > 1) {
		int mil = (2 * DEC + deb + fin) / 2 - DEC;
		
		pair<int, int> solOpt = calc(mil - 1);
		if(solOpt.second <= K) {
			fin = mil;
		}
		else {
			deb = mil;
		}
	}
	
	//cerr << deb << endl;
	// solOpt.second <= K
	
	pair<int, int> solOpt = calc(deb);
	cout << solOpt.first - deb * K << endl;
	return 0;
}

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct

Subtask #2
24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Correct	15 ms	340 KB	Output is correct
19	Correct	18 ms	340 KB	Output is correct
20	Correct	20 ms	340 KB	Output is correct
21	Correct	15 ms	340 KB	Output is correct
22	Correct	14 ms	340 KB	Output is correct
23	Correct	12 ms	304 KB	Output is correct
24	Correct	15 ms	344 KB	Output is correct
25	Correct	12 ms	340 KB	Output is correct
26	Correct	14 ms	300 KB	Output is correct
27	Correct	15 ms	344 KB	Output is correct
28	Correct	15 ms	340 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Correct	15 ms	340 KB	Output is correct
19	Correct	18 ms	340 KB	Output is correct
20	Correct	20 ms	340 KB	Output is correct
21	Correct	15 ms	340 KB	Output is correct
22	Correct	14 ms	340 KB	Output is correct
23	Correct	12 ms	304 KB	Output is correct
24	Correct	15 ms	344 KB	Output is correct
25	Correct	12 ms	340 KB	Output is correct
26	Correct	14 ms	300 KB	Output is correct
27	Correct	15 ms	344 KB	Output is correct
28	Correct	15 ms	340 KB	Output is correct
29	Correct	1266 ms	748 KB	Output is correct
30	Correct	1275 ms	780 KB	Output is correct
31	Correct	1331 ms	764 KB	Output is correct
32	Correct	1463 ms	884 KB	Output is correct
33	Correct	1409 ms	896 KB	Output is correct
34	Correct	1411 ms	760 KB	Output is correct
35	Correct	1168 ms	940 KB	Output is correct
36	Correct	1330 ms	736 KB	Output is correct
37	Correct	1361 ms	820 KB	Output is correct
38	Correct	1345 ms	884 KB	Output is correct
39	Correct	1309 ms	720 KB	Output is correct
40	Correct	1315 ms	836 KB	Output is correct
41	Correct	1339 ms	832 KB	Output is correct
42	Correct	1453 ms	864 KB	Output is correct

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Correct	15 ms	340 KB	Output is correct
19	Correct	18 ms	340 KB	Output is correct
20	Correct	20 ms	340 KB	Output is correct
21	Correct	15 ms	340 KB	Output is correct
22	Correct	14 ms	340 KB	Output is correct
23	Correct	12 ms	304 KB	Output is correct
24	Correct	15 ms	344 KB	Output is correct
25	Correct	12 ms	340 KB	Output is correct
26	Correct	14 ms	300 KB	Output is correct
27	Correct	15 ms	344 KB	Output is correct
28	Correct	15 ms	340 KB	Output is correct
29	Correct	1266 ms	748 KB	Output is correct
30	Correct	1275 ms	780 KB	Output is correct
31	Correct	1331 ms	764 KB	Output is correct
32	Correct	1463 ms	884 KB	Output is correct
33	Correct	1409 ms	896 KB	Output is correct
34	Correct	1411 ms	760 KB	Output is correct
35	Correct	1168 ms	940 KB	Output is correct
36	Correct	1330 ms	736 KB	Output is correct
37	Correct	1361 ms	820 KB	Output is correct
38	Correct	1345 ms	884 KB	Output is correct
39	Correct	1309 ms	720 KB	Output is correct
40	Correct	1315 ms	836 KB	Output is correct
41	Correct	1339 ms	832 KB	Output is correct
42	Correct	1453 ms	864 KB	Output is correct
43	Execution timed out	7101 ms	4388 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	300 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Correct	15 ms	340 KB	Output is correct
19	Correct	18 ms	340 KB	Output is correct
20	Correct	20 ms	340 KB	Output is correct
21	Correct	15 ms	340 KB	Output is correct
22	Correct	14 ms	340 KB	Output is correct
23	Correct	12 ms	304 KB	Output is correct
24	Correct	15 ms	344 KB	Output is correct
25	Correct	12 ms	340 KB	Output is correct
26	Correct	14 ms	300 KB	Output is correct
27	Correct	15 ms	344 KB	Output is correct
28	Correct	15 ms	340 KB	Output is correct
29	Correct	1266 ms	748 KB	Output is correct
30	Correct	1275 ms	780 KB	Output is correct
31	Correct	1331 ms	764 KB	Output is correct
32	Correct	1463 ms	884 KB	Output is correct
33	Correct	1409 ms	896 KB	Output is correct
34	Correct	1411 ms	760 KB	Output is correct
35	Correct	1168 ms	940 KB	Output is correct
36	Correct	1330 ms	736 KB	Output is correct
37	Correct	1361 ms	820 KB	Output is correct
38	Correct	1345 ms	884 KB	Output is correct
39	Correct	1309 ms	720 KB	Output is correct
40	Correct	1315 ms	836 KB	Output is correct
41	Correct	1339 ms	832 KB	Output is correct
42	Correct	1453 ms	864 KB	Output is correct
43	Execution timed out	7101 ms	4388 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-

Submission #776300

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 21.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
21.0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0