oj.uz

답안 #89552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89552 2018-12-15T15:48:55 Z kjain_1810 Go (COCI18_go) C++17
100 / 100
 482 ms 87064 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;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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