#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define pb push_back
#define INF 1023456789
#define maxn 305
int n,a[maxn],pv[maxn],nx[maxn];
vector<int> shop,play;
int memo[2*maxn][maxn];
int dp(int t,int i){
if(i>shop.size()||t>2*n)return 0;
if(memo[t][i]!=-1)return memo[t][i];
int num=0;
int sd=INF;
if(pv[i]!=-1)sd=min(sd,shop[i]-play[pv[i]]);
if(nx[i]<play.size())sd=min(sd,play[nx[i]]-shop[i]);
int cur=t,ans=0;
for(int x=0;x<=a[shop[i]];++x){
//back and forth x-1 times, then get 1 and go to another shop
if(cur>2*shop[i])break;
for(int y=i;y<=i+1;++y){
int take=INF;
if(x==0)take=min(take,abs(shop[y]-shop[i]));
if(pv[i]!=-1)take=min(take,abs(shop[y]-play[pv[i]])+abs(shop[i]-play[pv[i]]));
if(nx[i]<play.size())take=min(take,abs(shop[y]-play[nx[i]])+abs(shop[i]-play[nx[i]]));
if(y!=i)ans=max(ans,dp(cur+take,y)+x);
else ans=max(ans,x);
}
if(x>0)cur+=2*sd;
}
//pf("dp %d %d: %d\n",t,i,ans);
return memo[t][i]=ans;
}
int main(){
sf("%d",&n);
int sm=0;
for(int i=0;i<n;++i){
sf("%d",&a[i]);
if(a[i]==-1)play.pb(i);
else shop.pb(i),sm+=a[i];
}
if(shop.size()==0){
pf("0\n");
return 0;
}
int cur=-1;
for(int x=0;x<shop.size();++x){
int i=shop[x];
while(cur+1<play.size()&&play[cur+1]<i)++cur;
pv[x]=cur;
nx[x]=cur+1;
}
memset(memo,-1,sizeof memo);
pf("%d\n",sm-dp(shop[0],0));
}
Compilation message
tortoise.cpp: In function 'int dp(int, int)':
tortoise.cpp:16:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if(i>shop.size()||t>2*n)return 0;
| ~^~~~~~~~~~~~
tortoise.cpp:21:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | if(nx[i]<play.size())sd=min(sd,play[nx[i]]-shop[i]);
| ~~~~~^~~~~~~~~~~~
tortoise.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | if(nx[i]<play.size())take=min(take,abs(shop[y]-play[nx[i]])+abs(shop[i]-play[nx[i]]));
| ~~~~~^~~~~~~~~~~~
tortoise.cpp:18:6: warning: unused variable 'num' [-Wunused-variable]
18 | int num=0;
| ^~~
tortoise.cpp: In function 'int main()':
tortoise.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int x=0;x<shop.size();++x){
| ~^~~~~~~~~~~~
tortoise.cpp:55:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | while(cur+1<play.size()&&play[cur+1]<i)++cur;
| ~~~~~^~~~~~~~~~~~
tortoise.cpp:41:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | sf("%d",&n);
| ^
tortoise.cpp:44:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | sf("%d",&a[i]);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
1 ms |
980 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
980 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
980 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
1 ms |
980 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
980 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
980 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
1 ms |
980 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
980 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
980 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
1 ms |
980 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
980 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
980 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
1 ms |
980 KB |
Output is correct |
| 8 |
Correct |
1 ms |
980 KB |
Output is correct |
| 9 |
Correct |
1 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
980 KB |
Output is correct |
| 11 |
Correct |
1 ms |
980 KB |
Output is correct |
| 12 |
Correct |
1 ms |
980 KB |
Output is correct |
| 13 |
Correct |
1 ms |
980 KB |
Output is correct |
| 14 |
Correct |
1 ms |
980 KB |
Output is correct |
| 15 |
Correct |
1 ms |
980 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
