oj.uz

Submission #780495

# Submission time Handle Problem Language Result Execution time Memory
780495 2023-07-12T09:32:10 Z vjudge1 Go (COCI18_go) C++17
100 / 100
 227 ms 346368 KB 
// not greedy because dp :)))
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define OYY 2001
#define mod 998244353
int a[105],b[105],c[105];
int dp[105][105][2][2005];
int n,k,m,cev=0;

//tut => 0 left
//tut => 1 right
inline int d(int l,int r,int tut,int uz){
    if(l<1 || r>m)return 0;
    if(dp[l][r][tut][uz]!=-1)return dp[l][r][tut][uz] ;
    if(tut==0){
        int can=0;//şeker ekliyim?
        if(uz<c[l])can=b[l];
        dp[l][r][tut][uz]=max(dp[l][r][tut][uz] , d(l-1,r,0,min(abs(a[l-1]-a[l])+uz,(int)OYY))+can);
        dp[l][r][tut][uz]=max(dp[l][r][tut][uz] , d(l,r+1,1,min(abs(a[r+1]-a[l])+uz,(int)OYY))+can);
        //sola sağa
    }
    else{
        int can=0;
        if(uz<c[r])can=b[r];
        dp[l][r][tut][uz]=max(dp[l][r][tut][uz] , d(l-1,r,0,min(abs(a[l-1]-a[r])+uz,(int)OYY))+can);
        dp[l][r][tut][uz]=max(dp[l][r][tut][uz] , d(l,r+1,1,min(abs(a[r+1]-a[r])+uz,(int)OYY))+can);
    }
    return dp[l][r][tut][uz];
}

int32_t main(){
    faster
    memset(dp,-1,sizeof(dp));
    cin>>n>>k>>m;
    int sol=0,sag=0;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    for(int i=1;i<=m;i++){
        int deg=d(i,i,0,abs(a[i]-k));
        cev=max(cev,deg);
    }
    cout<<cev<<'\n';
    return 0;
}

Compilation message

go.cpp: In function 'int32_t main()':
go.cpp:37:9: warning: unused variable 'sol' [-Wunused-variable]
   37 |     int sol=0,sag=0;
      |         ^~~
go.cpp:37:15: warning: unused variable 'sag' [-Wunused-variable]
   37 |     int sol=0,sag=0;
      |               ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 346352 KB Output is correct
2 Correct 102 ms 346284 KB Output is correct
3 Correct 106 ms 346364 KB Output is correct
4 Correct 116 ms 346348 KB Output is correct
5 Correct 135 ms 346368 KB Output is correct
6 Correct 137 ms 346280 KB Output is correct
7 Correct 161 ms 346260 KB Output is correct
8 Correct 176 ms 346356 KB Output is correct
9 Correct 218 ms 346364 KB Output is correct
10 Correct 227 ms 346316 KB Output is correct