oj.uz

Submission #82840

# Submission time Handle Problem Language Result Execution time Memory
82840 2018-11-02T03:33:12 Z ngot23 Go (COCI18_go) C++11
100 / 100
 409 ms 86936 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11004 KB Output is correct
2 Correct 17 ms 15996 KB Output is correct
3 Correct 22 ms 19368 KB Output is correct
4 Correct 29 ms 24532 KB Output is correct
5 Correct 101 ms 49304 KB Output is correct
6 Correct 122 ms 57628 KB Output is correct
7 Correct 203 ms 65944 KB Output is correct
8 Correct 277 ms 74136 KB Output is correct
9 Correct 302 ms 82532 KB Output is correct
10 Correct 409 ms 86936 KB Output is correct