Submission #677202

#TimeUsernameProblemLanguageResultExecution timeMemory
677202Sandarach151Feast (NOI19_feast)C++17
18 / 100
98 ms262144 KiB
#include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; long long int arr[n]; int prev[n]; long long int maxx[n]; long long int ans[k][n]; for(int i=0; i<n; i++){ cin >> arr[i]; } maxx[0]=max(arr[0], (long long) 0); ans[0][0]=maxx[0]; prev[0]=-1; for(int i=1; i<n; i++){ maxx[i]=max(maxx[i-1]+arr[i], (long long) 0); ans[0][i]=max(maxx[i], ans[0][i-1]); if(maxx[i-1]+arr[i]>0){ prev[i]=prev[i-1]; } else{ prev[i]=i-1; } } for(int i=1; i<k; i++){ for(int j=0; j<n; j++){ if(prev[j]!=-1){ ans[i][j]=max(maxx[j]+ans[i-1][prev[j]], ans[i][j-1]); } else{ if(j==0){ ans[i][j]=maxx[0]; } else{ ans[i][j]=max(maxx[j], ans[i][j-1]); } } } } cout << ans[k-1][n-1] << '\n'; return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...