Submission #89552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89552	2018-12-15T15:48:55 Z	kjain_1810	Go (COCI18_go)	C++17	100 / 100	482 ms	87064 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 N=105;
const int inf=1000000000;
struct data {
    int p, val, t;
    bool operator < (const data &X) const {
        return t<X.t;
    }
} a[N];
int dp[2001][N][N], n, k, m;
 
void MAX(int &a, int b) {
    a=max(a, b);
}
 
int dd(int i, int j) {
    return a[j].p-a[i].p;
}
 
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 p, val, t;
        cin >> p >> val >> t;
        a[i]={p, val, t};
    }
    rep(i, 0, 2000)
        rep(j, 1, m)
            rep(k, 1, m) dp[i][j][k]=-inf;
    rep(i, 1, m) {
        int dis=abs(k-a[i].p);
        int add=0;
        if(dis<a[i].t) add=a[i].val;
        dp[dis][i][i]=add;
    }
    rep(i, 0, 2000)
        rep(j, 1, m-1)
            rep(k, j+1, m) {
                int add=(i<a[j].t?a[j].val:0);
                if(i-dd(j, j+1)>=0) {
                    MAX(dp[i][j][k], dp[i-dd(j, j+1)][j+1][k]+add);
                }
                if(i-dd(j, k)>=0) {
                    MAX(dp[i][j][k], dp[i-dd(j, k)][k][j+1]+add);
                }
                add=(i<a[k].t?a[k].val:0);
                if(i-dd(k-1, k)>=0) {
                    MAX(dp[i][k][j], dp[i-dd(k-1, k)][k-1][j]+add);
                }
                if(i-dd(j, k)>=0) {
                    MAX(dp[i][k][j], dp[i-dd(j, k)][j][k-1]+add);
                }
            }
    int ans=0;
    rep(i, 0, 2000) {
        MAX(ans, dp[i][1][m]);
        MAX(ans, dp[i][m][1]);
    }
    cout << ans;
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11000 KB	Output is correct
2	Correct	15 ms	16128 KB	Output is correct
3	Correct	18 ms	19508 KB	Output is correct
4	Correct	28 ms	24472 KB	Output is correct
5	Correct	95 ms	49348 KB	Output is correct
6	Correct	132 ms	57544 KB	Output is correct
7	Correct	199 ms	65880 KB	Output is correct
8	Correct	293 ms	74376 KB	Output is correct
9	Correct	334 ms	82444 KB	Output is correct
10	Correct	482 ms	87064 KB	Output is correct