Submission #672204

#TimeUsernameProblemLanguageResultExecution timeMemory
672204CutebolK blocks (IZhO14_blocks)C++17
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> using namespace std; //void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} #define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0); #define int long long #define itn int #define endl "\n" #define ff first #define cout cerr #define ss second const int N = 2e5 + 5 ; const int mod = 1e9 + 7 ; const int inf = 1e12 ; int n , m ; int a[N] ; int dp[104][N] ; void solve(){ cin >> n >> m ; 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 <= m ; i ++ ) for ( int j = 1 ; j <= n; j ++ ) dp[i][j] = inf ; for ( int i = 2 ; i <= m ; i ++ ){ stack <pair<int,int>> st ; for ( int j = i ; j <= n ; j ++ ){ int last = dp[i-1][j-1] ; while ( !st.empty() && st.top().ff <= a[j] ){ last = min ( last , st.top().ss ) ; st.pop() ; } if ( st.empty() || st.top().ff <= a[j] ) st.push({a[j],last}) ; dp[i][j] = min ( last + a[j] , st.top().ff + st.top().ss ) ; } } cout << dp[m][n] ; } signed main(){ // fopn("talent") ; // Scaramouche ; int t = 1 ; // cin >> t ; while ( t -- ) solve() ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...