Submission #1198760

#TimeUsernameProblemLanguageResultExecution timeMemory
11987604o2aK blocks (IZhO14_blocks)C++17
100 / 100
450 ms82344 KiB
#include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define _F "test" using namespace std; typedef long long ll; constexpr ll INF = 1e18; int n, k; ll st[200001]; void upd(int pos, ll val) { for (st[pos += n] = val; pos > 1; pos >>= 1) st[pos>>1] = min(st[pos], st[pos^1]); } ll getmin(int l, int r) { ll res = INF; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) res = min(res, st[l++]); if (r&1) res = min(res, st[--r]); } return res; } void solve() { cin>>n>>k; vector<int> val(n+1), pre(n+1); val[0] = 10000000; stack<int> temp; temp.push(0); vector<vector<ll>> dp(k+1, vector<ll>(n+1, INF)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { cin>>val[i]; while (val[i] >= val[temp.top()]) temp.pop(); pre[i] = temp.top(); temp.push(i); } dp[1][1] = val[1]; for (int i = 2; i <= n; ++i) dp[1][i] = max(dp[1][i-1], (ll)val[i]); for (int i = 2; i <= k; ++i) { for (int j = 1; j <= n; ++j) upd(j, val[j] + dp[i-2][j-1]); for (int j = i; j <= n; ++j) { dp[i][j] = min({dp[i][pre[j]], dp[i-1][j-1] + val[j], val[j] + getmin(pre[j]+1, j)}); } } cout<<dp[k][n]; } int main() { if (fopen(_F".INP", "r")) { freopen(_F".INP", "r", stdin); //freopen(_F".OUT", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); int Test = 1; //cin>>Test; while (Test--) solve(); }

Compilation message (stderr)

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