Submission #698188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698188	2023-02-12T19:15:52 Z	BidoTeima	Go (COCI18_go)	C++17	30 / 100	345 ms	314520 KB

go

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
using ll = long long;
ll dp[105][105][2005][2];
ll a[105], b[105], t[105];
int n, k, m;
ll cost(int i, int j, bool onWho, bool toWho) {
	//to i - 1
	if (!toWho) { 
		if (i == 0)return -1;
		if (!onWho) {
			return a[i] - a[i - 1];
		}
		return a[j] - a[i - 1];
	}
	// to j + 1
	if (j == m - 1)return -1;
	if (!onWho) {
		return a[j + 1] - a[i];
	}
	return a[j + 1] - a[j];
}
int main()
{ 
	cin >> n >> k >> m; 
	for (int i = 0; i < m; i++)
		cin >> a[i] >> b[i] >> t[i];
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 2005; k++) {
				dp[i][j][k][0] = dp[i][j][k][1] = -1e18;
			}
		}
	}
	ll nearest_left = -1, nearest_right = -1;
	for (int i = 0; i < m && a[i] <= k; i++) {
		nearest_left = i;
	}
	for (int i = m - 1; i >= 0 && a[i] >= k; i--) {
		nearest_right = i;
	}
	ll dist, ans=0;
	if (nearest_left != -1) {
		dist = k - a[nearest_left];
		dp[nearest_left][nearest_left][dist][1] =
		dp[nearest_left][nearest_left][dist][0] = (dist < t[nearest_left] ? b[nearest_left] : 0);
		ans = max(ans, dp[nearest_left][nearest_left][dist][1]);
	}
	if (nearest_right != -1) {
		dist = a[nearest_right] - k;
		dp[nearest_right][nearest_right][dist][1] =
		dp[nearest_right][nearest_right][dist][0] = (dist < t[nearest_right] ? b[nearest_right] : 0);
		ans = max(ans, dp[nearest_right][nearest_right][dist][1]);
	}
	for (int i = 0; i < m; i++) {
		for (int x = 0; i + x < m; x++) {
			int j = i + x;
			for (int curTime = 0; curTime < 2003; curTime++) {
				for (int on = 0; on < 2; on++) {
					ans = max(ans, dp[i][j][curTime][on]);
					// 0 means on i, 1 means on j
					// option 1: transition to [i - 1][j] 
					int v = cost(i, j, on, 0);
					if (i > 0 && curTime + v <= 2003) {
						int tot = curTime + v;
						dp[i - 1][j][tot][0] = max(dp[i - 1][j][tot][0],
							dp[i][j][curTime][on] + (tot < t[i - 1] ? b[i - 1] : 0));
						ans = max(ans, dp[i - 1][j][tot][0]);
					}
					// option 2: transition to [i][j + 1]
					v = cost(i, j, on, 1);
					if (j < m - 1 && curTime + v <= 2003) {
						int tot = curTime + v;
						dp[i][j + 1][tot][1] = max(dp[i][j + 1][tot][1],
							dp[i][j][curTime][on] + (tot < t[j + 1] ? b[j + 1] : 0)); 
						ans = max(ans, dp[i][j + 1][tot][1]);
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	724 KB	Output isn't correct
2	Incorrect	4 ms	3412 KB	Output isn't correct
3	Correct	7 ms	6580 KB	Output is correct
4	Correct	13 ms	13012 KB	Output is correct
5	Incorrect	84 ms	79048 KB	Output isn't correct
6	Correct	120 ms	113644 KB	Output is correct
7	Incorrect	162 ms	154520 KB	Output isn't correct
8	Incorrect	215 ms	201632 KB	Output isn't correct
9	Incorrect	267 ms	254876 KB	Output isn't correct
10	Incorrect	345 ms	314520 KB	Output isn't correct