oj.uz

Submission #241514

# Submission time Handle Problem Language Result Execution time Memory
241514 2020-06-24T10:48:31 Z NONAME Go (COCI18_go) C++14
100 / 100
 198 ms 173304 KB 
#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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 173048 KB Output is correct
2 Correct 108 ms 173048 KB Output is correct
3 Correct 107 ms 173048 KB Output is correct
4 Correct 93 ms 173304 KB Output is correct
5 Correct 123 ms 173176 KB Output is correct
6 Correct 120 ms 173048 KB Output is correct
7 Correct 140 ms 173048 KB Output is correct
8 Correct 166 ms 173176 KB Output is correct
9 Correct 198 ms 173188 KB Output is correct
10 Correct 152 ms 173048 KB Output is correct