Submission #1060347

#TimeUsernameProblemLanguageResultExecution timeMemory
10603470pt1mus23K blocks (IZhO14_blocks)C++14
0 / 100
5 ms59996 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ins insert #define pb push_back #define int long long int #define pii pair<int, int> #define endl '\n' #define drop(x) cout<<(x)<<endl; return; #define all(x) x.begin(),x.end() #define hash z0hashp #define div z0dvp const int mod = 1e9 +7, sze = 1e6+23, inf = LLONG_MAX, P = 1453; int dp[200][100000]; //https://codeforces.com/blog/entry/18866?#comment-238114 void opt1z(){ int n,k; cin>>n>>k; vector<int> arr(n+1); int mx =0; for(int i=0;i<=n;i++){ for(int j=0;j<=k;j++){ dp[i][j]=0x3f; } } for(int i=1;i<=n;i++){ cin>>arr[i]; mx=max(mx,arr[i]); dp[1][i]=mx; } for(int i=2;i<=k;i++){ stack<int> s1,s2; for(int j=1;j<=n;j++){ int mdp =dp[i-1][j-1]; while(!s1.empty() && s1.top()<arr[j]){ mdp = min(mdp,s2.top()); s2.pop(); s1.pop(); } if(s1.empty() || mdp+ arr[j]<s1.top() + s2.top()){ s1.push(arr[j]); s2.push(mdp); } if(j>=i){ dp[i][j]=s1.top() + s2.top(); // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl; } } } drop(dp[k][n]); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; // cin>>tt; while(tt--){ opt1z(); } 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...