Submission #780855

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
780855	2023-07-12T14:00:50 Z	vjudge1	Go (COCI18_go)	C++17	40 / 100	312 ms	319952 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 N 200005

int n,k,m;
vector<tuple<int,int,int>> pokemon;
ll int dp[2][2001][101][101];
ll int sagda(int ,int ,int ,int);
ll int solda(int nerden, int sn,int left,int right){
	if(sn>2000)return 0;
	int yedek=nerden;
	if(left<0||left>=m)return 0;
	if(dp[nerden][sn][left][right]!=-1)return dp[nerden][sn][left][right];
	if(nerden==0)nerden=left;
	else  nerden=right;

	int f,d,e,x,y,z;
	tie(f,d,e)=pokemon[nerden];
	ll int a=0,b=0;
	

	if(left>0){
		tie(x,y,z)=pokemon[left-1];
		a=solda(0,sn+abs(f-x),left-1,right);
		if(sn+abs(f-x)<z)a+=y;
	}
	if(right<m-1){
		tie(x,y,z)=pokemon[right+1];
		b=sagda(0,sn+abs(f-x),left,right+1);
		if(sn+abs(f-x)<z)b+=y;
	}
	return dp[yedek][sn][left][right]=max(a,b);
}
ll int sagda(int nerden,int sn,int left,int right){
	if(sn>2000)return 0;
	int yedek=nerden;
	if(left<0||left>=m)return 0;
	if(dp[nerden][sn][left][right]!=-1)return dp[nerden][sn][left][right];
	if(nerden==0)nerden=left;
	else nerden=right;

	int f,d,e,x,y,z;
	tie(f,d,e)=pokemon[nerden];
	ll int a=0,b=0;


	if(left>0){
		tie(x,y,z)=pokemon[left-1];
		a=solda(0,sn+abs(f-x),left-1,right);
		if(sn+abs(f-x)<z)a+=y;
	}
	if(right<m-1){
		tie(x,y,z)=pokemon[right+1];
		b=sagda(1,sn+abs(f-x),left,right+1);
		if(sn+abs(f-x)<z)b+=y;
	}
	return dp[yedek][sn][left][right]=max(a,b);
}
int main(){
	lalala;
	memset(dp,-1,sizeof(dp));
	cin>>n>>k>>m;
	int le, rr;
	le=rr=-1;
	for(int i=0;i<m;i++){
		ll int a,b,c;cin>>a>>b>>c;		
		pokemon.pb({a,b,c});
		if(a>k&&rr==-1)rr=i;
		else if(a<k)le=i;
	}
	ll int a=0,b=0;
	if(le!=-1){
		int x,y,z;
		tie(x,y,z)=pokemon[le];
		a=solda(0,abs(x-k),le,le);
		if(abs(x-k)<z)a+=y;
	}
	if(rr!=-1){
		int x,y,z;
		tie(x,y,z)=pokemon[rr];
		b=solda(0,abs(x-k),rr,rr);
		if(abs(x-k)<z)b+=y;
	}
	cout<<max(a,b)<<endl;



}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	319820 KB	Output is correct
2	Correct	128 ms	319804 KB	Output is correct
3	Correct	136 ms	319952 KB	Output is correct
4	Correct	129 ms	319744 KB	Output is correct
5	Incorrect	175 ms	319836 KB	Output isn't correct
6	Incorrect	175 ms	319772 KB	Output isn't correct
7	Incorrect	204 ms	319936 KB	Output isn't correct
8	Incorrect	242 ms	319868 KB	Output isn't correct
9	Incorrect	312 ms	319784 KB	Output isn't correct
10	Incorrect	263 ms	319872 KB	Output isn't correct