# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
544011 | ala2 | Go (COCI18_go) | C++14 | 281 ms | 479748 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
//#define first first
//#define second second
#define pb push_back
#define B begin()
#define E end()
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
vector < pair< int ,pair<int,int> > >v;
const int inf=1e16;
int n,k;
int dp[101][101][2001][3];
const int rr=2001;
int d(int i,int j)
{
return abs( v[i].first-v[j].first );
}
int f(int l,int r,int t,int bo)
{if(t>2000)
return 0;
if(l==0&&r==n-1)
return 0;
if(l<0)
return -inf;
if(r>=n)
return -inf;
if(dp[l][r][t][bo]!=-1)
return dp[l][r][t][bo];
// cout<<" "<<2<<endl;
if(bo==0)
{
int one=f(l-1,r,min(rr,t+d(l-1,l)),0)+( (t+d(l-1,l)<v[l-1].second.second)*v[l-1].second.first );
int tow=0;
if(r+1<n)
tow=f(l,r+1,min(rr,t+d(l,r+1)),1)+( (t+d(l,r+1)<v[r+1].second.second)*v[r+1].second.first );
return dp[l][r][t][bo]=max(one,tow);
}
if(bo==1)
{
int one=f(l-1,r,min(rr,t+d(l-1,r)),0)+( (t+d(l-1,r)<v[l-1].second.second)*v[l-1].second.first );
int tow=0;
if(r+1<n)
tow=f(l,r+1,min(rr,t+d(r,r+1)),1)+( (t+d(r,r+1)<v[r+1].second.second)*v[r+1].second.first );
return dp[l][r][t][bo]=max(one,tow);
}
}
signed main()
{
//int n,k;
memset(dp,-1,sizeof dp);
map<int,int>m;
cin>>n>>k>>n;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
m[x]=1;
v.pb( {x,{y,z}} );
}
v.pb( {k,{0,0}} );
n++;
sort(v.B,v.E);
for(int i=0;i<n;i++)
{
if(v[i].first==k&&v[i].second.first==0&&v[i].second.second==0)
{
cout<<f(i,i,0,0)<<endl;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |