Submission #410730

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410730	2021-05-23T14:18:18 Z	snasibov05	Go (COCI18_go)	C++14	60 / 100	590 ms	524292 KB

go

#include <iostream>
#include <vector>

using namespace std;

struct data{
    int x;
    int c;
    int t;
};

const int tmax = 2005;

int calc(int l, int r, int t, int lst, int n,vector<data>& v, vector<vector<vector<vector<int>>>>& dp){

    if (t >= tmax || l < 0 || r >= n) return 0;
    if (dp[l][r][t][lst] != -1) return dp[l][r][t][lst];

    int res = 0;
    if (lst == 0){
        res = max(res, calc(l-1, r, t + (v[l].x - v[l-1].x), 0, n,  v, dp));
        res = max(res, calc(l, r+1, t + (v[r+1].x - v[l].x), 1, n, v, dp));
        if (t < v[l].t) res += v[l].c;
    } else{
        res = max(res, calc(l-1, r, t + (v[r].x - v[l-1].x), 0, n, v, dp));
        res = max(res, calc(l, r+1, t + (v[r+1].x - v[r].x), 1, n, v, dp));
        if (t < v[r].t) res += v[r].c;
    }

    return dp[l][r][t][lst] = res;

}

int main() {

    int n, k, m; cin >> n >> k >> m;
    vector<data> v(n);
    for (int i = 0; i < m; ++i) {
        cin >> v[i].x >> v[i].c >> v[i].t;
    }

    vector<vector<vector<vector<int>>>> dp(m, vector<vector<vector<int>>>(m, vector<vector<int>>(tmax, vector<int>(2, -1))));

    int ans = 0;
    for (int i = 0; i < m; ++i){
        ans = max(ans, calc(i, i, abs(k - v[i].x), 0, m, v, dp));
    }

    cout << ans << "\n";



    return 0;
}

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2508 KB	Output is correct
2	Correct	16 ms	12408 KB	Output is correct
3	Correct	30 ms	23424 KB	Output is correct
4	Correct	62 ms	46528 KB	Output is correct
5	Correct	489 ms	280620 KB	Output is correct
6	Correct	590 ms	402496 KB	Output is correct
7	Runtime error	460 ms	524292 KB	Execution killed with signal 9
8	Runtime error	453 ms	524292 KB	Execution killed with signal 9
9	Runtime error	464 ms	524292 KB	Execution killed with signal 9
10	Runtime error	464 ms	524292 KB	Execution killed with signal 9