Submission #742472

#TimeUsernameProblemLanguageResultExecution timeMemory
742472jamielimTortoise (CEOI21_tortoise)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; typedef vector<int> vi; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int n,arr[500005]; vector<int> v; int dist[500005]; int dp[305][605]; // max number of candies removed for (last shop taken from, time) int main(){ scanf("%d",&n); int sum=0; for(int i=0;i<n;i++){ scanf("%d",&arr[i]); if(arr[i]==-1)v.pb(i); else sum+=arr[i]; } for(int i=0;i<n;i++){ if(arr[i]!=-1){ int x=lower_bound(ALL(v),i)-v.begin(); dist[i]=abs(v[x]-i); if(x!=0)dist[i]=min(abs(v[x-1]-i),dist[i]); } } if(arr[0]==1){ for(int j=0;j<=600;j++){ dp[0][j]=1; } }else{ for(int j=0;j<=600;j++){ dp[0][j]=-INF; } } for(int i=1;i<n;i++){ if(arr[i]==1){ for(int j=0;j<=600;j++){ if(j<i)dp[i][j]=0; if(j==i)dp[i][j]=1; if(j>i){ dp[i][j]=1; for(int k=0;k<i;k++){ if(j>=dist[i]+dist[k]){ dp[i][j]=max(dp[i][j],dp[k][j-dist[i]-dist[k]]+1); } } } } }else{ for(int j=0;j<=600;j++)dp[i][j]=-INF; } } printf("%d",sum-dp[n-1][2*n-2]); }

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
tortoise.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...