Submission #1198681

#TimeUsernameProblemLanguageResultExecution timeMemory
11986814o2aK blocks (IZhO14_blocks)C++20
0 / 100
14 ms23880 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; ll st[400001]; void upd(int v, int tl, int tr, int pos, ll val) { if (tl == tr) st[v] = val; else { int tm = (tl+tr)/2; if (pos <= tm) upd(2*v, tl, tm, pos, val); else upd(2*v+1, tm+1, tr, pos, val); st[v] = min(st[2*v], st[2*v+1]); } } ll getmin(int v, int tl, int tr, int l, int r) { if (l > r) return INF; if (l <= tl && tr <= r) return st[v]; int tm = (tl+tr)/2; return min(getmin(2*v, tl, tm, l, min(r, tm)), getmin(2*v+1, tm+1, tr, max(l, tm+1), r)); } void solve() { int n, k, cur = 0, app = 1; cin>>n>>k; vector<int> val(n+1), pre(n+1); val[0] = 10000000; vector<vector<int>> idx(1000001); 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]; idx[val[i]].pb(i); if (val[i] > cur) { cur = val[i]; app = 1; } else if (val[i] == cur) ++app; dp[1][i] = app*cur; while (val[i] >= val[temp.top()]) temp.pop(); pre[i] = temp.top(); temp.push(i); } for (int i = 2; i <= k; ++i) { for (int j = 1; j <= n; ++j) upd(1, 1, n, 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]); if (pre[j]+1 < j) { auto x1 = lower_bound(idx[val[j]].begin(), idx[val[j]].end(), j); auto x2 = lower_bound(idx[val[j]].begin(), idx[val[j]].end(), pre[j]+1); int cnt = x1 - x2 + 1; if (cnt > 1) dp[i][j] = min(dp[i][j], dp[i][j-1] + val[j]); int pos = max((x1 == idx[val[j]].begin() ? 0 : *prev(x1)), pre[j]); dp[i][j] = min(dp[i][j], getmin(1, 1, n, pos+1, j-1) + val[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:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         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...