# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
241514 | NONAME | Go (COCI18_go) | C++14 | 198 ms | 173304 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int n, k, m, dp[105][105][2001][2];
pair <int, pair <int, int> > a[105];
int solve(int l, int r, int t, bool rev) {
if (t > 2000)
return 0;
if (dp[l][r][t][rev] != -1)
return dp[l][r][t][rev];
int &cur = dp[l][r][t][rev];
cur = 0;
auto it = (rev == 0 ? a[l] : a[r]);
if (l - 1 >= 1)
cur = max(cur, solve(l - 1, r, t + it.first - a[l - 1].first, 0));
if (r + 1 <= m)
cur = max(cur, solve(l, r + 1, t + a[r + 1].first - it.first, 1));
cur += (it.second.second > t ? it.second.first : 0);
return cur;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k >> m;
for (int i = 1; i <= m; ++i)
cin >> a[i].first >> a[i].second.first >> a[i].second.second;
a[++m] = make_pair(k, make_pair(0, 0));
sort(a + 1, a + m + 1);
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= m; ++i)
if (a[i].first == k)
return cout << solve(i, i, 0, 0), 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |