Submission #1060357

#TimeUsernameProblemLanguageResultExecution timeMemory
10603570pt1mus23K blocks (IZhO14_blocks)C++14
0 / 100
1 ms2396 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[105][100005]; 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[j][i]=inf; } } 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 md = dp[i-1][j-1]; while(!s1.empty() && s1.top() < arr[j]){ md = min(md,s2.top()); s1.pop(); s2.pop(); } if(s1.empty() || md + arr[j] < s1.top() + s2.top()){ s1.push(arr[j]); s2.push(md); } if(j>=i){ dp[i][j] = s1.top() + s2.top(); } } } 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...