Submission #231168

#TimeUsernameProblemLanguageResultExecution timeMemory
231168infinite_iqK blocks (IZhO14_blocks)C++14
53 / 100
1092 ms8588 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 547 //#define mp make_pair #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() typedef long long ll; typedef short int si; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll inf=1e18; const ll mod=1e9+7; const ld pai=acos(-1); int n , k ; int a[100009]; int dp[100009][209] ; int main () { cin >> n >> k ; for ( int i = 1 ; i <= n ; i ++ ) { cin >> a[i] ; dp [i][1] = max ( dp[i-1][1] , a[i] ) ; } dp[0][1] = 1e9 ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 2 ; j <= k ; j ++ ) { dp [i][j] = 1e9 ; } } for ( int j = 2 ; j <= k ; j ++ ) { for ( int i = j ; i <= n ; i ++ ) { int mx = 0 ; for ( int it = i ; it >= 1 ; it -- ) { mx = max ( mx , a[it] ) ; if ( mx != a[i] ) { dp [i][j] = min ( dp[i][j] , dp[it][j] ) ; break ; } dp [i][j] = min ( dp [i][j] , dp [it-1][j-1] + a[i] ) ; } } } cout << dp[n][k] << 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...