Submission #269932

# Submission time Handle Problem Language Result Execution time Memory
269932 2020-08-17T11:21:04 Z kaplanbar Go (COCI18_go) C++14
60 / 100
2 ms 384 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pk {
    ll a, b, t;
    bool operator<(const Pk other) const {
        return a < other.a;
    }
};
ll n, k, m, sz1, sz2;;
Pk v1[105],v2[105];
int mx[2005];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> m;
    for(int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        if(a>k) v1[sz1++]={a,b,t};
        else v2[sz2++]={a,b,t};
        mx[a] = max(mx[a], b);
    }
    sort(v1, v1+sz1);
    
    sort(v2, v2+sz2);
    reverse(v2, v2+sz2);

    ll ans = 0;

    ll s = 0;

    vector<bool> vis(2005,0);

    for(int i = 0; i < sz1; i++) {
        if(v1[i].t > v1[i].a - k) s += v1[i].b;

        int tim = (v1[i].a - k) * 2;

        ll s2 = 0;

        for(int j = 0; j < sz2; j++) {
            if(v2[j].t > k - v2[j].a  + tim && !vis[v2[j].a]) {
                s2 += mx[v2[j].a];
                vis[v2[j].a];
            }
        }

        ans = max(ans, s + s2);
    }

    for(int i = 0; i < 2005; i++) vis[i] = 0;

    s = 0;

    for(int i = 0; i < sz2; i++) {
        if(v2[i].t > k - v2[i].a) s += v2[i].b;

        int tim = (k - v2[i].a) * 2;

        ll s2 = 0;

        for(int j = 0; j < sz1; j++) {
            if(v1[j].t > v1[j].a - k + tim && !vis[v1[j].a]) {
                s2 += mx[v1[j].a];
                vis[v1[j].a] = 1;
            }
        }

        ans = max(ans, s + s2);
    }

    cout << ans;

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Incorrect 0 ms 384 KB Output isn't correct