Submission #226887

#TimeUsernameProblemLanguageResultExecution timeMemory
226887DavidDamianSličice (COCI19_slicice)C++11
90 / 90
344 ms1528 KiB
#include <bits/stdc++.h> using namespace std; ///Dynamic Programming ///Determine the maximum number of points when adding some extra images int memo[505][505]; int A[505]; int B[1005]; int sum[505]; int points(int i,int k) { if(i==0) return 0; if(k==0) return sum[i]; if(memo[i][k]==-1){ for(int j=0;j<=k;j++){ memo[i][k]=max(memo[i][k],points(i-1,k-j) +B[ A[i]+j ]); } } return memo[i][k]; } int n,m,k; int main() { memset(memo,-1,sizeof(memo)); cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>A[i]; } for(int i=0;i<=m;i++){ cin>>B[i]; } for(int i=m+1;i<=2*m+1;i++){ B[i]=B[i-1]; } for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+B[ A[i] ]; } cout<<points(n,k)<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...