답안 #776306

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776306	2023-07-07T15:59:08 Z	hugo_pm	Chorus (JOI23_chorus)	C++17	61 / 100	930 ms	1048576 KB

chorus

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

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }

using pii = pair<int, int>;
using vi = vector<int>;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
	bool first = true;
	string res = "[";
	for (const auto &x : v) {
		if (!first)
			res += ", ";
		first = false;
		res += to_string(x);
	}
	res += "]";
	return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
	cout << ' ' << to_string(H);
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

int N, K;
string S;
const int INF = 1e12;
// ferme[i] = nombre d'ouvrants avant Fi
vector<int> ouvre, ferme;
vector<int> cumuFerme;
int coutInclus(int left, int right) {
	if (left > right) {
		return 0;
	}
	int projExclus = min(right+1, ouvre[right]);
	if (projExclus <= left) return 0;
	return (projExclus - left)*(right+1) - (cumuFerme[projExclus] - cumuFerme[left]);
}

vector<vector<int>> dp;
// cur et opt inclus
// mais cur représente right exclus
void calc(int nbCoup, int curLeft, int curRight, int optLeft, int optRight) {
	if (curLeft > curRight) return;
	int curMid = (curLeft + curRight) / 2;
	pair<int, int> p {INF, -1};
	rep(coupe, optLeft, optRight+1) {
		chmin(p, {dp[nbCoup-1][coupe] + coutInclus(coupe, curMid-1), coupe});
	}
	dp[nbCoup][curMid] = p.first;
	int optMid = p.second;
	calc(nbCoup, curLeft, curMid-1, optLeft, optMid);
	calc(nbCoup, curMid+1, curRight, optMid, optRight);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> K >> S;
	{
		int curOuvre = 0, curFerme = 0;
		cumuFerme.push_back(0);
		for (char c : S) {
			if (c == 'A') {
				++curOuvre;
				ouvre.push_back(curFerme);
			} else {
				++curFerme;
				ferme.push_back(curOuvre);
				cumuFerme.push_back(cumuFerme.back() + curOuvre);
			}
		}
	}

	dp = vector<vector<int>>(K+1, vector<int>(N+1, INF));
	dp[0][0] = 0;
	rep(nbCoup, 1, K+1) {
		calc(nbCoup, 0, N, 0, N-1);
	}
	cout << dp[K][N] << '\n';
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 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	0 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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 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	0 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	1 ms	340 KB	Output is correct
18	Correct	2 ms	596 KB	Output is correct
19	Correct	4 ms	1364 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	6 ms	2260 KB	Output is correct
23	Correct	7 ms	2260 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	7 ms	2260 KB	Output is correct
26	Correct	6 ms	1876 KB	Output is correct
27	Correct	3 ms	980 KB	Output is correct
28	Correct	3 ms	980 KB	Output is correct

Subtask #3

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 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	0 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	1 ms	340 KB	Output is correct
18	Correct	2 ms	596 KB	Output is correct
19	Correct	4 ms	1364 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	6 ms	2260 KB	Output is correct
23	Correct	7 ms	2260 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	7 ms	2260 KB	Output is correct
26	Correct	6 ms	1876 KB	Output is correct
27	Correct	3 ms	980 KB	Output is correct
28	Correct	3 ms	980 KB	Output is correct
29	Correct	327 ms	79484 KB	Output is correct
30	Correct	930 ms	170284 KB	Output is correct
31	Correct	226 ms	40788 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	1 ms	656 KB	Output is correct
34	Correct	716 ms	196488 KB	Output is correct
35	Correct	718 ms	196480 KB	Output is correct
36	Correct	3 ms	980 KB	Output is correct
37	Correct	267 ms	39756 KB	Output is correct
38	Correct	619 ms	162604 KB	Output is correct
39	Correct	537 ms	93788 KB	Output is correct
40	Correct	260 ms	65876 KB	Output is correct
41	Correct	264 ms	65884 KB	Output is correct
42	Correct	251 ms	65856 KB	Output is correct

Subtask #4

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 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	0 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	1 ms	340 KB	Output is correct
18	Correct	2 ms	596 KB	Output is correct
19	Correct	4 ms	1364 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	6 ms	2260 KB	Output is correct
23	Correct	7 ms	2260 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	7 ms	2260 KB	Output is correct
26	Correct	6 ms	1876 KB	Output is correct
27	Correct	3 ms	980 KB	Output is correct
28	Correct	3 ms	980 KB	Output is correct
29	Correct	327 ms	79484 KB	Output is correct
30	Correct	930 ms	170284 KB	Output is correct
31	Correct	226 ms	40788 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	1 ms	656 KB	Output is correct
34	Correct	716 ms	196488 KB	Output is correct
35	Correct	718 ms	196480 KB	Output is correct
36	Correct	3 ms	980 KB	Output is correct
37	Correct	267 ms	39756 KB	Output is correct
38	Correct	619 ms	162604 KB	Output is correct
39	Correct	537 ms	93788 KB	Output is correct
40	Correct	260 ms	65876 KB	Output is correct
41	Correct	264 ms	65884 KB	Output is correct
42	Correct	251 ms	65856 KB	Output is correct
43	Runtime error	510 ms	1048576 KB	Execution killed with signal 9
44	Halted	0 ms	0 KB	-

Subtask #5

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 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	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 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	0 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	1 ms	340 KB	Output is correct
18	Correct	2 ms	596 KB	Output is correct
19	Correct	4 ms	1364 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	6 ms	2260 KB	Output is correct
23	Correct	7 ms	2260 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	7 ms	2260 KB	Output is correct
26	Correct	6 ms	1876 KB	Output is correct
27	Correct	3 ms	980 KB	Output is correct
28	Correct	3 ms	980 KB	Output is correct
29	Correct	327 ms	79484 KB	Output is correct
30	Correct	930 ms	170284 KB	Output is correct
31	Correct	226 ms	40788 KB	Output is correct
32	Correct	1 ms	596 KB	Output is correct
33	Correct	1 ms	656 KB	Output is correct
34	Correct	716 ms	196488 KB	Output is correct
35	Correct	718 ms	196480 KB	Output is correct
36	Correct	3 ms	980 KB	Output is correct
37	Correct	267 ms	39756 KB	Output is correct
38	Correct	619 ms	162604 KB	Output is correct
39	Correct	537 ms	93788 KB	Output is correct
40	Correct	260 ms	65876 KB	Output is correct
41	Correct	264 ms	65884 KB	Output is correct
42	Correct	251 ms	65856 KB	Output is correct
43	Runtime error	510 ms	1048576 KB	Execution killed with signal 9
44	Halted	0 ms	0 KB	-