oj.uz

답안 #98246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98246 2019-02-21T16:46:38 Z dalgerok Go (COCI18_go) C++17
100 / 100
 295 ms 173304 KB 
#include<bits/stdc++.h>
using namespace std;



int n, k, m, dp[105][105][2001][2];
pair < int, pair < int, int > > a[106];


int rec(int l, int r, int t, bool rev){
    if(t > 2000){
        return 0;
    }
    if(dp[l][r][t][rev] != -1){
        return dp[l][r][t][rev];
    }
    int &cur = dp[l][r][t][rev];
    cur = 0;
    auto it = (rev == 0 ? a[l] : a[r]);
    if(l - 1 >= 1){
        cur = max(cur, rec(l - 1, r, t + it.first - a[l - 1].first, 0));
    }
    if(r + 1 <= m){
        cur = max(cur, rec(l, r + 1, t + a[r + 1].first - it.first, 1));
    }
    cur += (it.second.second > t ? it.second.first : 0);
    return cur;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i].first >> a[i].second.first >> a[i].second.second;
    }
    a[++m] = make_pair(k, make_pair(0, 0));
    sort(a + 1, a + m + 1);
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= m; i++){
        if(a[i].first == k){
            return cout << rec(i, i, 0, 0), 0;
        }
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 173048 KB Output is correct
2 Correct 147 ms 173304 KB Output is correct
3 Correct 138 ms 173048 KB Output is correct
4 Correct 144 ms 173176 KB Output is correct
5 Correct 156 ms 172984 KB Output is correct
6 Correct 152 ms 173048 KB Output is correct
7 Correct 245 ms 172952 KB Output is correct
8 Correct 237 ms 173144 KB Output is correct
9 Correct 295 ms 173048 KB Output is correct
10 Correct 233 ms 173052 KB Output is correct