Submission #1248117

#TimeUsernameProblemLanguageResultExecution timeMemory
1248117kokokaiK blocks (IZhO14_blocks)C++20
100 / 100
272 ms166004 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5+4; ll a[N]; ll dp[N][105]; ll dp1[N][105]; ll n,K; void solve(){ memset(dp,0x3f3f3f3f,sizeof dp); memset(dp1,0x3f3f3f3f,sizeof dp1); cin>>n>>K; for(int i=1;i<=n;i++) cin>>a[i]; dp[0][0]=0; for(int k=1;k<=K;k++){ vector<int> st; dp1[k][k]=dp[k-1][k-1]; //dp1[i][k]=luu min cac dp[p+1...i][k-1] voi a[p]>a[i] for(int i=k;i<=n;i++){ while(!st.empty() && a[st.back()] <= a[i]){ dp1[i][k]=min(dp1[i][k],dp1[st.back()][k]); st.pop_back(); } dp[i][k]=min(dp[i][k],dp1[i][k]+a[i]); int i1=0; if(!st.empty()) i1=st.back(); dp[i][k]=min(dp[i][k],dp[i1][k-1]+a[i]); dp1[i][k]=min(dp1[i][k],dp[i][k-1]); dp[i][k]=min(dp[i][k],dp[i1][k]); st.push_back(i); } } cout<<dp[n][K]<<'\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); if(fopen("text.inp","r")){ freopen("text.inp","r",stdin); } int tt=1; //cin>>tt; while(tt--){ solve(); } }

Compilation message (stderr)

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