| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 780522 |
2023-07-12T09:50:33 Z |
vjudge1 |
Go (COCI18_go) |
C++17 |
|
372 ms |
524288 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
int n,k,m;
vector<tuple<int,ll int,int>> pokemon;
ll int dp[2][2000][100][100];
ll int sagda(int ,ll int , int ,int);
ll int solda(int nerden, ll int sn,int left,int right){
int yedek=nerden;
if(left<0||left>right)return 0;
if(nerden!=2&&dp[nerden][sn][left][right]!=-1)return dp[nerden][sn][left][right];
if(nerden==0)nerden=left-1;
else if(nerden==1)nerden=right;
else nerden=k;
ll int f,x,y,z;
if(nerden!=k)tie(f,x,y)=pokemon[nerden];
else f=k;
ll int ans=0,a=0,b=0;
tie(x,y,z)=pokemon[left];
if(abs(x-f)+sn<z){
a=y+solda(0,sn+abs(x-f),left-1,right);
b=y+sagda(0,sn+abs(x-f),left,right+1);
}
else a=solda(0,sn+abs(x-f),left-1,right);
//cout<<endl<<x<<" "<<y<<" "<<z<<" "<<f<<endl;
//cout<<nerden<<" "<<yedek<<" a "<<sn<<" "<<left<<" "<<right<<" "<<a<<" "<<b<<endl;
if(yedek!=2)return dp[yedek][sn][left][right]=max(a,b);
return max(a,b);
}
ll int sagda(int nerden,ll int sn,int left,int right){
int yedek=nerden;
if(right>=m||left>right)return 0;
if(nerden!=2&&dp[nerden][sn][left][right]!=-1)return dp[nerden][sn][left][right];
if(nerden==0)nerden=left;
else if(nerden==1)nerden=right-1;
else nerden=k;
ll int f,x,y,z;
if(nerden!=k)tie(f,x,y)=pokemon[nerden];
else f=k;
ll int ans=0,a=0,b=0;
tie(x,y,z)=pokemon[right];
if(abs(x-f)+sn<z){
a=y+sagda(1,sn+abs(x-f),left,right+1);
b=y+solda(1,sn+abs(x-f),left-1,right);
}
else a=sagda(1,sn+abs(x-f),left,right+1);
//cout<<endl<<x<<" "<<y<<" "<<z<<" "<<f<<endl;
//cout<<nerden<<" "<<yedek<<" b "<<sn<<" "<<left<<" "<<right<<" "<<a<<" "<<b<<endl;
if(yedek!=2)return dp[yedek][sn][left][right]=max(a,b);
return max(a,b);
}
int main(){
lalala;
memset(dp,-1,sizeof(dp));
int mm;cin>>n>>k>>mm;
ll int cev=0;
int le, rr;
le=rr=-1;
for(int i=0;i<mm;i++){
ll int a,b,c;cin>>a>>b>>c;
if(a==k){
cev+=b;
continue;
}
if(abs(k-a)<c){
pokemon.pb({a,b,c});
if(a>k&&rr==-1)rr=m;
else if(a<k)le=m;
m++;
}
}
if(rr==-1)rr=m+1;
if(le==-1)le=-1;
//cout<<solda(2,0,le,rr-1)<<endl;//<<sagda(2,0,le+1,rr)<<endl;
cout<<max(solda(2,0,le,rr-1),sagda(2,0,le+1,rr))+cev<<endl;
}
Compilation message
go.cpp: In function 'long long int solda(int, long long int, int, int)':
go.cpp:22:9: warning: unused variable 'ans' [-Wunused-variable]
22 | ll int ans=0,a=0,b=0;
| ^~~
go.cpp: In function 'long long int sagda(int, long long int, int, int)':
go.cpp:47:9: warning: unused variable 'ans' [-Wunused-variable]
47 | ll int ans=0,a=0,b=0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
95 ms |
313384 KB |
Output is correct |
| 2 |
Correct |
106 ms |
313340 KB |
Output is correct |
| 3 |
Incorrect |
94 ms |
313348 KB |
Output isn't correct |
| 4 |
Correct |
96 ms |
313332 KB |
Output is correct |
| 5 |
Incorrect |
101 ms |
313364 KB |
Output isn't correct |
| 6 |
Incorrect |
97 ms |
313404 KB |
Output isn't correct |
| 7 |
Runtime error |
372 ms |
524288 KB |
Execution killed with signal 11 |
| 8 |
Incorrect |
102 ms |
313292 KB |
Output isn't correct |
| 9 |
Incorrect |
95 ms |
313352 KB |
Output isn't correct |
| 10 |
Runtime error |
360 ms |
524288 KB |
Execution killed with signal 11 |
