#include <iostream>
#include <vector>
using namespace std;
int dp[105][105][2005][2];
int a[105], b[105], t[105];
int n, k, m;
int 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] = - 1e9;
}
}
}
int nearest_left = 0, nearest_right = 0;
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;
}
int 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);
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);
int ans = 0;
/*for (int aaa = 0; aaa < 15; aaa++)*/ 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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
1876 KB |
Output isn't correct |
| 3 |
Correct |
5 ms |
3412 KB |
Output is correct |
| 4 |
Correct |
11 ms |
6724 KB |
Output is correct |
| 5 |
Incorrect |
65 ms |
39764 KB |
Output isn't correct |
| 6 |
Correct |
98 ms |
57120 KB |
Output is correct |
| 7 |
Incorrect |
127 ms |
77528 KB |
Output isn't correct |
| 8 |
Incorrect |
171 ms |
101104 KB |
Output isn't correct |
| 9 |
Incorrect |
210 ms |
127820 KB |
Output isn't correct |
| 10 |
Incorrect |
259 ms |
157784 KB |
Output isn't correct |
