Submission #639670

#TimeUsernameProblemLanguageResultExecution timeMemory
639670classicGo (COCI18_go)C++14
100 / 100
257 ms160204 KiB
#include <bits/stdc++.h> using namespace std; const int M = 100; const int K = 2000; int dp[M + 1][M + 1][K + 1][2]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k, m; cin >> n >> k >> m; vector<int> a(m), b(m), t(m); for (int i = 0; i < m; i++) { cin >> a[i] >> b[i] >> t[i]; } memset(dp, -1, sizeof(dp)); function<int(int, int, int, int)> rec = [&](int l, int r, int diff, int pos) { if (diff > 2001) { return 0; } int &ret = dp[l][r][diff][pos == a[l] ? 0 : 1]; if (ret >= 0) { return ret; } ret = 0; if (l > 0) { int diffNext = diff + abs(pos - a[l - 1]); if (diffNext < t[l - 1]) { ret = max(ret, rec(l - 1, r, diffNext, a[l - 1]) + b[l - 1]); } else { ret = max(ret, rec(l - 1, r, diffNext, a[l - 1])); } } if (r < m - 1) { int diffNext = diff + abs(pos - a[r + 1]); if (diffNext < t[r + 1]) { ret = max(ret, rec(l, r + 1, diffNext, a[r + 1]) + b[r + 1]); } else { ret = max(ret, rec(l, r + 1, diffNext, a[r + 1])); } } return ret; }; int res = 0; for (int start = 0; start < m; start++) { int diff = abs(a[start] - k); if (diff < t[start]) { res = max(res, rec(start, start, diff, a[start]) + b[start]); } else { res = max(res, rec(start, start, diff, a[start])); } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...