Submission #134136

#TimeUsernameProblemLanguageResultExecution timeMemory
134136mirbek01K blocks (IZhO14_blocks)C++11
0 / 100
13 ms1528 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, a[N], k, dp[102][N]; int stk[N], pt, pf[N]; int main(){ cin >> n >> k; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++){ dp[1][i] = max(dp[1][i - 1], a[i]); } for(int i = 2; i <= k; i ++){ pt = 0; deque < pair <int, int> > dq; for(int j = i; j <= n; j ++){ while(pt > 0 && a[ stk[pt] ] < a[j]) pt --; stk[++ pt] = j; while(!dq.empty() && dq.front().second < max(stk[pt - 1], i - 1)) dq.pop_front(); while(!dq.empty() && dq.back().first > dp[i - 1][j - 1]) dq.pop_back(); dq.push_back({dp[i - 1][j - 1], j - 1}); pf[pt] = dq.front().first + a[j]; if(pt > 1) pf[pt] = min(pf[pt - 1], pf[pt]); dp[i][j] = pf[pt]; } } cout << dp[k][n] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...