제출 #1271323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271323		model_code	Heat Stroke (JOI24_heat)	C++20	64 / 100	2096 ms	48456 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];
		}
		auto getsum = [&](int l, int r) -> int {
			return s[r] - s[l];
		};
		vector<vector<int> > ndp(g[i].size() + 1, vector<int>(N + 1, -INF));
		for (int j = 0; j <= g[i].size(); j++) {
			for (int k = 0; k <= N; k++) {
				for (int x = 0; x <= (i != 0 ? g[i - 1].size() : 0); x++) {
					for (int y = 0; y <= N; y++) {
						if (dp[x][y] != -INF) {
							int b = getsum(0, max(k, y));
							int z = b - j;
							bool f = true;
							if (j > C[i + 1]) f = false;
							if (j < (y < k ? getsum(y, k) : 0)) f = false;
							if (z < (k < y ? getsum(k, y) : 0)) f = false;
							if (y != N ? x + z != C[i] : x + z > C[i]) f = false;
							if (f) {
								ndp[j][k] = max(ndp[j][k], dp[x][y] + getsum(max(k, y), N));
							}
						}
					}
				}
			}
		}
		dp = ndp;
	}

	// step #3. final
	int ans = -INF;
	for (int i = 0; i <= 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: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 25 / 25
• Subtask 5: 25 / 25
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 5