Submission #780837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780837	2023-07-12T13:46:39 Z	DangerNoodle7591	Go (COCI18_go)	C++17	100 / 100	198 ms	326368 KB

go

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define endl "\n"
#define ll long long
#define pb push_back
#define M 102
ll int deg[M],yer[M],dak[M];
ll int n,m,k;
ll int dp[2][2002][M][M];
ll int hesap(int nerde,ll int sn,int left,int right){
	if(sn>2000)return 0;
	if(left<0||right>=m)return 0;
	if(dp[nerde][sn][left][right]!=-1)return dp[nerde][sn][left][right];
	ll int a=0,b=0;
	if(nerde==0){//leftteyim
		if(left>0){
			a=hesap(nerde,sn+abs(yer[left]-yer[left-1]),left-1,right);
			if(abs(yer[left]-yer[left-1])+sn<dak[left-1])a+=deg[left-1];
		}
		if(right<m-1){
			b=hesap(1,sn+abs(yer[left]-yer[right+1]),left,right+1);
			if(abs(yer[left]-yer[right+1])+sn<dak[right+1])b+=deg[right+1];
		}
		//cout<<nerde<<" "<<a<<" "<<b<<" "<<sn<<" "<<left<<" "<<right<<endl;
		return dp[nerde][sn][left][right]=max(a,b);
	}
	if(left>0){
		a=hesap(0,sn+abs(yer[right]-yer[left-1]),left-1,right);
		if(abs(yer[right]-yer[left-1])+sn<dak[left-1])a+=deg[left-1];
	}
	if(right<m-1){
		b=hesap(1,sn+abs(yer[right]-yer[right+1]),left,right+1);
		if(abs(yer[right]-yer[right+1])+sn<dak[right+1])b+=deg[right+1];
	}
	//cout<<nerde<<" "<<a<<" "<<b<<" "<<sn<<" "<<left<<" "<<right<<endl;
	return dp[nerde][sn][left][right]=max(a,b);
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>k>>m;
	int yes=0;
	ll int cev=0;
	int l=-1,r=-1;
	for(int i=0;i<m;i++){
		cin>>yer[i]>>deg[i]>>dak[i];
		if(yer[i]<k)l=i;
		else if(r==-1)r=i;
	}
	ll int a=0,b=0;
	if(l!=-1){
		a=hesap(0,abs(k-yer[l]),l,l);
		if(abs(k-yer[l])<dak[l])a+=deg[l];
	}
	if(r!=-1){
		b=hesap(1,abs(k-yer[r]),r,r);
		if(abs(k-yer[r])<dak[r])b+=deg[r];
	}
	cout<<max(a,b)<<endl;
}

Compilation message

go.cpp: In function 'int main()':
go.cpp:42:6: warning: unused variable 'yes' [-Wunused-variable]
   42 |  int yes=0;
      |      ^~~
go.cpp:43:9: warning: unused variable 'cev' [-Wunused-variable]
   43 |  ll int cev=0;
      |         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	326308 KB	Output is correct
2	Correct	98 ms	326364 KB	Output is correct
3	Correct	97 ms	326348 KB	Output is correct
4	Correct	102 ms	326340 KB	Output is correct
5	Correct	150 ms	326356 KB	Output is correct
6	Correct	126 ms	326368 KB	Output is correct
7	Correct	153 ms	326260 KB	Output is correct
8	Correct	164 ms	326316 KB	Output is correct
9	Correct	198 ms	326252 KB	Output is correct
10	Correct	164 ms	326304 KB	Output is correct