Submission #1274765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274765		khanhgng	K blocks (IZhO14_blocks)	C++20	100 / 100	213 ms	191244 KiB

blocks

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x.size()))
#define pb push_back
#define bit(i,x) ((x>>i)&1)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define task "test"

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r){assert(l<=r);return uniform_int_distribution<ll>(l,r)(rd);}

const int MAXn = 2e5 + 10;
const ll INF = (long long)(1e18);
const ll MOD1 = 1e9;
const int MOD = 1e9 + 7;
const int BL = 340;
const int BASE = 3137;

int n,k,a[MAXn],dp[121][MAXn];
stack<pii>st;

void solution(){
    cin>>n>>k;
    FOR(i,1,n)cin>>a[i];
    memset(dp,0x3f,sizeof(dp));
    dp[1][1]=a[1];
    FOR(i,2,n){
        dp[1][i]=max(dp[1][i-1],a[i]);
    }
    FOR(x,2,k){
        while(!st.empty()){st.pop();}
        FOR(i,1,n){
            int best=dp[x-1][i-1];
            while(!st.empty()&&a[st.top().se]<=a[i]){
                best=min(best,st.top().fi);
                st.pop();
            }
            dp[x][i]=min(dp[x][i],a[i]+best);
            if(!st.empty()){
                dp[x][i]=min(dp[x][i],dp[x][st.top().se]);
            }
            st.push({best,i});
        }
    }
    cout << dp[k][n];
}

///cs1: dp[x][i]=dp[x][j] (j gan i nhat va a[j]>a[i])
///cs2: dp[x][i]=dp[x-1][k-1]+a[i] (voi moi k de a[i] lam max)

int32_t main(){
    if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
    ios_base::sync_with_stdio(0);cin.tie(0);
    int Ntest=1;///cin>>Ntest;
    while(Ntest--)solution();
    cerr<< "\n" << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
}

Compilation message (stderr)

blocks.cpp: In function 'int32_t main()':
blocks.cpp:60:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
      |                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:60:68: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     if(fopen(task".inp","r")){freopen(task".inp","r",stdin);freopen(task".out","w",stdout);}
      |                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47