oj.uz

Submission #776306

# Submission time Handle Problem Language Result Execution time Memory
776306 2023-07-07T15:59:08 Z hugo_pm Chorus (JOI23_chorus) C++17
61 / 100
 930 ms 1048576 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -