답안 #780871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780871 2023-07-12T14:10:01 Z DangerNoodle7591 Go (COCI18_go) C++17
90 / 100
237 ms 320076 KB
    #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||right>=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);
    }
    ll int sagda(int nerden,int sn,int left,int right){
    	if(sn>2000)return 0;
    	int yedek=nerden;
    	if(left<0||right>=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=sagda(1,abs(x-k),rr,rr);
    		if(abs(x-k)<z)b+=y;
    	}
    	cout<<max(a,b)<<endl;
     
     
     
    }
# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 319820 KB Output is correct
2 Correct 129 ms 319872 KB Output is correct
3 Correct 131 ms 319748 KB Output is correct
4 Correct 128 ms 319816 KB Output is correct
5 Correct 160 ms 319864 KB Output is correct
6 Correct 158 ms 319820 KB Output is correct
7 Correct 206 ms 319872 KB Output is correct
8 Correct 208 ms 319768 KB Output is correct
9 Correct 237 ms 319820 KB Output is correct
10 Incorrect 218 ms 320076 KB Output isn't correct