Submission #239699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
239699	2020-06-17T07:57:08 Z	ne4eHbKa	Go (COCI18_go)	C++17	90 / 100	68 ms	29864 KB

go

#include <bits/stdc++.h>
using namespace std;

template<typename t> void umax(t &a, t b) {a = max(a, b);}

int n, m, k;

void solve() {
    cin >> n >> k >> m;
    const int mt = 2020;
    struct pok {
        int x, t, c;
        bool operator< (const pok &f) const {
            return x < f.x;
        }
        int go(int d) {
            return d <= t ? c : 0;
        }
    };
    vector<pok> le, ri;
    le.push_back({0, 0, 0});
    ri.push_back({0, 0, 0});
    for(int i = 0; i < m; ++i) {
        int a, b, t;
        cin >> a >> b >> t;
        if(a < k) {
            le.push_back({k - a, t - 1, b});
        } else {
            ri.push_back({a - k, t - 1, b});
        }
    }
    sort(le.begin(), le.end());
    sort(ri.begin(), ri.end());
    int l = le.size();
    int r = ri.size();
    int ans = 0;
    int f[l][r][mt][2];
    memset(f, -1, sizeof f);
    f[0][0][0][0] = 0;
    for(int i = 0; i < l; ++i) {
        for(int j = 0; j < r; ++j) {
            for(int t = 0; t < mt; ++t) {
                for(int side : {0, 1}) {
                    int &g = f[i][j][t][side];
                    if(g < 0) continue;
                    umax(ans, g);
                    int px = side ? ri[j].x : le[i].x;
                    if(i + 1 < l) {
                        pok &p = le[i + 1];
                        int dist = t + p.x + (side ? +1 : -1) * px;
                        if(dist < mt) umax(f[i + 1][j][dist][0], g + p.go(dist));
                    }
                    if(j + 1 < r) {
                        pok &p = ri[j + 1];
                        int dist = t + p.x + (side ? -1 : +1) * px;
                        if(dist < mt) umax(f[i][j + 1][dist][1], g + p.go(dist));
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cerr << "case #" << i << endl;
        solve();
        cerr << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
#endif
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	640 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	6 ms	1280 KB	Output is correct
5	Correct	25 ms	10240 KB	Output is correct
6	Correct	22 ms	11532 KB	Output is correct
7	Correct	43 ms	20224 KB	Output is correct
8	Correct	51 ms	24704 KB	Output is correct
9	Correct	68 ms	29864 KB	Output is correct
10	Incorrect	54 ms	26240 KB	Output isn't correct