Submission #239702

#	Time	Username	Problem	Language	Result	Execution time	Memory
239702		ne4eHbKa	Go (COCI18_go)	C++17	90 / 100	80 ms	59128 KiB

go

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

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

typedef long long ll;
#define int ll

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

signed 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 / 100