Submission #1247901

#TimeUsernameProblemLanguageResultExecution timeMemory
1247901free_de_la_zenithK blocks (IZhO14_blocks)C++20
100 / 100
117 ms18404 KiB
/** * author: MINHTPC * **/ #include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(a) a.begin() , a.end() #define FOR(i ,a , b) for(int i = a ; i <= b ; ++i) #define bit(mask,i) ((mask>>i)&1) #define name "task" #define lo lower_bound #define up upper_bound #define count_bit1(x) __builtin_popcountll(x) #define count_bit01(x) __builtin_clzll(x) #define count_bit10(x) __builtin_ctzll(x) using namespace std; const int N=1e6+5; const long long INF=1e18; using pii=pair<ll,ll>; long long a[N],dp[N],f[N],L[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); if(fopen("umnik.inp","r")) { freopen("umnik.inp","r",stdin); // freopen("umnik.out","w",stdout); } int n,k; cin >> n >> k; for(int i=1;i<=n;i++) cin >> a[i]; stack<int>s; for(int i=1;i<=n;i++) { while(!s.empty() && a[s.top()]<=a[i]) s.pop(); L[i]=s.empty()?1:s.top()+1; s.push(i); } memset(f,60,sizeof f); memset(dp,60,sizeof dp); f[1]=a[1]; for(int i=2;i<=n;i++) f[i]=max(f[i-1],a[i]); for(int j=2;j<=k;j++) { stack<pii>st; for(int i=1;i<=n;i++) { dp[i]=dp[L[i]-1]; long long mn=f[i-1]; while(!st.empty() && st.top().se<=a[i]) { mn=min(mn,st.top().fi); st.pop(); } dp[i]=min(dp[i],mn+a[i]); st.push({mn,a[i]}); } for(int i=1;i<=n;i++) { f[i]=dp[i]; dp[i]=INF; } } cout << f[n]; }

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("umnik.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...