Submission #698170

#TimeUsernameProblemLanguageResultExecution timeMemory
698170BidoTeimaGo (COCI18_go)C++17
50 / 100
1099 ms157588 KiB
#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 < 10; aaa++)for (int i = 0; i < m; i++) { for (int j = i; j < m; j++) { 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] = 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] = 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...