Submission #82840

#	Time	Username	Problem	Language	Result	Execution time	Memory
82840		ngot23	Go (COCI18_go)	C++11	100 / 100	409 ms	86936 KiB

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

//79 3 6
//20 65 23
//36 29 37
//33 23 54
//52 92 56
//48 6 59
//59 97 101

• Subtask 1: 100 / 100