Submission #1247909

#TimeUsernameProblemLanguageResultExecution timeMemory
1247909_dtq_K blocks (IZhO14_blocks)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define sz(x) (ll)(x.size()) #define all(v) v.begin(), v.end() #define sz(x) (ll)(x.size()) #define se second #define fi first using namespace std; const ll N = 1e5 + 9; const ll M = 109; ll n, i, j, k, bit[M][N], dp[N][M], a[N]; void up( ll x, ll y, ll val ) { while(y <= n) { bit[x][y] = min(bit[x][y], val); y += (y & (-y)); } } ll get( ll x, ll y ) { if(x == 0) return 1e18; ll maxn = 1e18; while(y > 0) { maxn = min(maxn, bit[x][y]); y -= (y & (-y)); } return maxn; } int main() { #define TN "blocks" if(fopen(TN ".in", "r")) { freopen(TN ".inp", "r", stdin); freopen(TN ".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); cin >> n >> k; for( i = 1; i <= n; i ++ ) cin >> a[i]; stack<ll>f; for( i = 1; i <= n; i ++ ) for( int j = 1; j <= k; j ++ ) bit[j][i] = 1e18; for( i = 1; i <= n; i ++ ) { ll vt = 0; while(sz(f) && a[f.top()] <= a[i]) f.pop(); if(sz(f)) vt = f.top(); if(vt == 0) { for( int w = 1; w <= min(i, k); w ++) { if(w == 1) dp[i][w] = a[i]; else dp[i][w] = a[i] + get(w - 1, n); } } else { for( int w = 1; w <= min(i, k); w ++ ) dp[i][w] = min(dp[vt][w], a[i] + get(w - 1, n - vt)); } f.push(i); for( int w = 1; w <= min(i, k); w ++ ) up(w, n - i + 1, dp[i][w]); } cout << dp[n][k]; return 0; } /* */

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(TN ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...