Submission #780495

#	Time	Username	Problem	Language	Result	Execution time	Memory
780495		vjudge1	Go (COCI18_go)	C++17	100 / 100	227 ms	346368 KiB

go

// 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 (stderr)

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 / 100