Submission #82835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82835	2018-11-02T01:33:31 Z	ngot23	Go (COCI18_go)	C++11	40 / 100	44 ms	1640 KB

go

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int inf=1000000000;
struct data {
    int p, val, t;
    bool operator < (const data &X) const {
        return t<X.t;
    }
} e[105];
int dp[105][2001], n, m, k, maxt;

void MAX(int &a, int b) {
    a=max(a, b);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n >> k >> m;
    rep(i, 1, m) {
        int pos, val, t;
        cin >> pos >> val >> t;
        e[i]={pos, val, t};
    }
    sort(e+1, e+m+1);
    maxt=e[m].t;
    rep(i, 0, m)
        rep(j, 0, maxt) dp[i][j]=-inf;
    e[0]={k, 0, 0};
    dp[0][0]=0;
    rep(i, 1, m)
        rep(t, 0, maxt)
            rep(j, 0, i-1) {
                int dis=abs(e[i].p-e[j].p);
                if(t<dis||dp[j][t-dis]==-inf) continue;
                if(t>=e[i].t) MAX(dp[i][t], dp[j][t-dis]);
                else MAX(dp[i][t], dp[j][t-dis]+e[i].val);
            }
    int ans=0;
    rep(i, 1, m)
        rep(j, 0, maxt)
            MAX(ans, dp[i][j]);
    cout << ans;
    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	584 KB	Output is correct
3	Incorrect	2 ms	680 KB	Output isn't correct
4	Correct	3 ms	812 KB	Output is correct
5	Correct	9 ms	1176 KB	Output is correct
6	Incorrect	13 ms	1300 KB	Output isn't correct
7	Incorrect	19 ms	1300 KB	Output isn't correct
8	Incorrect	26 ms	1424 KB	Output isn't correct
9	Incorrect	33 ms	1428 KB	Output isn't correct
10	Incorrect	44 ms	1640 KB	Output isn't correct