Submission #1271324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271324		model_code	Heat Stroke (JOI24_heat)	C++20	100 / 100	466 ms	502160 KiB

heat

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solve(int L, int N, const vector<int>& C, const vector<int>& A) {
	// step #1. preparation
	vector<vector<int> > g(L - 1);
	for (int i = 0; i < N; i++) {
		g[A[i]].push_back(i);
	}

	// step #2. dynamic programming
	const int INF = 1012345678;
	vector<vector<int> > dp(1, vector<int>(N + 1, 0));
	for (int i = 0; i <= L - 2; i++) {
		vector<int> s(N + 1);
		for (int j = 0; j < N; j++) {
			if (A[j] == i) {
				s[j + 1]++;
			}
		}
		for (int j = 0; j < N; j++) {
			s[j + 1] += s[j];
		}
		int sn = g[i].size();
		int sp = (i != 0 ? g[i - 1].size() : 0);
		vector<vector<int> > ndp(sn + 1, vector<int>(N + 1, -INF));
		// pattern A: dp[?][y] -> dp[j][k] (0 <= y < k) [d = s[k] - j]
		for (int d = max(C[i] - sp, 0); d <= min(sn, C[i]); d++) {
			int x = C[i] - d;
			int val = -INF;
			for (int j = 0; j <= min(sn - d, C[i + 1]); j++) {
				for (int k = (d + j != 0 ? g[i][d + j - 1] + 1 : 0); k <= (d + j != sn ? g[i][d + j] : N); k++) {
					if (val != -INF) {
						ndp[j][k] = max(ndp[j][k], val + sn - (d + j));
					}
					val = max(val, dp[x][k]);
				}
			}
		}
		// pattern B: dp[?][y] -> dp[j][k] (k <= y < N)
		for (int j = 0; j <= min(sn, C[i + 1]); j++) {
			int val = -INF;
			for (int k = N - 1; k >= (j != 0 ? g[i][j - 1] + 1 : 0); k--) {
				int x = C[i] - (s[k] - j);
				if (0 <= x && x <= sp && dp[x][k] != -INF) {
					val = max(val, dp[x][k] + sn - s[k]);
				}
				ndp[j][k] = max(ndp[j][k], val);
			}
		}
		// pattern C: dp[?][N] -> dp[j][k]
		for (int j = 0; j <= min(sn, C[i + 1]); j++) {
			int val = -INF;
			for (int x = 0; x <= min(sp, C[i] + j - sn); x++) {
				val = max(val, dp[x][N]);
			}
			for (int k = (j != 0 ? g[i][j - 1] + 1 : 0); k <= N; k++) {
				ndp[j][k] = max(ndp[j][k], val);
			}
		}
		dp = ndp;
	}

	// step #3. final
	int ans = -INF;
	for (int i = 0; i <= int(g[L - 2].size()); i++) {
		for (int j = 0; j <= N; j++) {
			if (j != N ? i == C[L - 1] : i <= C[L - 1]) {
				ans = max(ans, dp[i][j]);
			}
		}
	}

	return ans;
}

int main() {
	int L;
	cin >> L;
	vector<int> C(L);
	for (int i = 0; i < L; i++) {
		cin >> C[i];
	}
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]--;
	}
	int ans = solve(L, N, C, A);
	cout << ans << endl;
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 25 / 25
• Subtask 5: 25 / 25
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 5 / 5