Submission #639670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
639670	2022-09-11T01:14:22 Z	classic	Go (COCI18_go)	C++14	100 / 100	257 ms	160204 KB

go

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	159976 KB	Output is correct
2	Correct	61 ms	159968 KB	Output is correct
3	Correct	66 ms	159980 KB	Output is correct
4	Correct	59 ms	159996 KB	Output is correct
5	Correct	89 ms	160092 KB	Output is correct
6	Correct	89 ms	160024 KB	Output is correct
7	Correct	146 ms	160204 KB	Output is correct
8	Correct	176 ms	160096 KB	Output is correct
9	Correct	222 ms	159976 KB	Output is correct
10	Correct	257 ms	160100 KB	Output is correct