답안 #239702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239702 2020-06-17T07:59:51 Z ne4eHbKa Go (COCI18_go) C++17
90 / 100
80 ms 59128 KB
#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
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Correct 27 ms 20096 KB Output is correct
6 Correct 26 ms 22656 KB Output is correct
7 Correct 51 ms 40192 KB Output is correct
8 Correct 60 ms 48888 KB Output is correct
9 Correct 80 ms 59128 KB Output is correct
10 Incorrect 66 ms 52224 KB Output isn't correct