oj.uz

Submission #707287

# Submission time Handle Problem Language Result Execution time Memory
707287 2023-03-08T18:01:21 Z aedmhsn Go (COCI18_go) C++17
60 / 100
 131 ms 173324 KB 
#include <bits/stdc++.h>
using namespace std;
 
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);

const int mxN=5e3+5;

int dp[105][105][2005][2], t[105], v[105], h[105], n, m, k;

// left = 1, right = 0;
int solve(int l, int r, int time, bool dir){
    if(dp[l][r][time][dir] != -1)
        return dp[l][r][time][dir];
    int ret1=0, ret2=0;
    if(dir){
        if(l-1 >= 1)
            ret1 = solve(l-1, r, time+abs(h[l]-h[l-1]), 1)+(time + abs(h[l]-h[l-1]) < t[l-1] ? v[l-1]:0);
        if(r <= m)
            ret2 = solve(l-1, r, time+abs(h[l]-h[r]), 0) + (time + abs(h[l]-h[r]) < t[r] ? v[r]:0);
        
        return dp[l][r][time][dir]=max(ret1, ret2);
    }
    else{
        if(l >= 1)
            ret1 = solve(l, r+1, time+abs(h[r]-h[l]), 1)+(time + abs(h[r]-h[l]) < t[l] ? v[l]:0);
        if(r+1 <= m)
            ret2 = solve(l, r+1, time+abs(h[r]-h[r+1]), 0) + (time + abs(h[r]-h[r+1]) < t[r+1] ? v[r+1]:0);
        return dp[l][r][time][dir]=max(ret1, ret2);
    }

}

int main(){
    ms(dp , -1);
    cin >> n >> k >> m;
    int st=-1;
    for(int i=1; i<=m; i++){
        cin >> h[i] >> v[i] >> t[i];
        if(h[i] >= k && st==-1)
            st=i;
    }
    if(st == -1)
        cout << solve(m-1, m, (k-h[m]), 0) + (abs(k-h[m]) < t[m] ? v[m]:0);
    else
        cout << max(solve(st-1, st, abs(k-h[st-1]), 1)+(abs(k-h[st-1]) < t[st-1] ? v[st-1]:0), solve(st-1, st, abs(k-h[st]), 0) + (abs(k-h[st]) < t[st] ? v[st]:0));
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 173312 KB Output is correct
2 Correct 61 ms 173264 KB Output is correct
3 Incorrect 63 ms 173304 KB Output isn't correct
4 Correct 68 ms 173264 KB Output is correct
5 Incorrect 77 ms 173256 KB Output isn't correct
6 Correct 79 ms 173324 KB Output is correct
7 Incorrect 128 ms 173260 KB Output isn't correct
8 Correct 128 ms 173220 KB Output is correct
9 Incorrect 127 ms 173300 KB Output isn't correct
10 Correct 131 ms 173300 KB Output is correct