oj.uz

답안 #639670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639670 2022-09-11T01:14:22 Z classic Go (COCI18_go) C++14
100 / 100
 257 ms 160204 KB 
#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

# 결과 실행 시간 메모리 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