#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 |
