Submission #1282250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282250		quan606303	K blocks (IZhO14_blocks)	C++20	53 / 100	817 ms	327680 KiB

blocks

/*
 * @Author: RMQuan 
 * @Date: 2025-10-22 23:48:40 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-23 01:00:46
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=1e5+7;
const int inf=1e18;
int a[maxn],n,k;
int L[maxn],R[maxn];
struct ST
{
    int N;
    vector<int> st,lazy;
    ST(int n):N(n),st(4*n+5,inf),lazy(4*n+5,inf){}
    void fix(int id,int l,int r)
    {
        if (lazy[id]>=inf)return ;
        st[id]=min(st[id],lazy[id]);
        if (l!=r)
        {
            lazy[id*2]=min(lazy[id*2],lazy[id]);
            lazy[id*2+1]=min(lazy[id*2+1],lazy[id]);
        }
        lazy[id]=inf;
    }
    void upd(int id,int l,int r,int u,int v,int val)
    {
        fix(id,l,r);
        if (l>v||r<u)return ;
        if (l>=u&&r<=v)
        {
            lazy[id]=min(lazy[id],val);
            fix(id,l,r);
            return ;
        }
        int mid=(l+r)/2;
        upd(id*2,l,mid,u,v,val);
        upd(id*2+1,mid+1,r,u,v,val);
        st[id]=min(st[id*2],st[id*2+1]);
    }
    int get(int id,int l,int r,int u,int v)
    {
        fix(id,l,r);
        if (l>v||r<u)return inf;
        if (l>=u&&r<=v)return st[id];
        int mid=(l+r)/2;
        return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
};
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>k;
    for (int i=1;i<=n;i++)cin>>a[i];  
    stack<int> st;
    for (int i=1;i<=n;i++)
    {
        while (st.size()&&a[st.top()]<=a[i])st.pop();
        if (st.size())L[i]=st.top()+1;
        else L[i]=1;
        st.push(i);
    }
    while (st.size())st.pop();
    for (int i=n;i>=1;i--)
    {
        while(st.size()&&a[st.top()]<=a[i])st.pop();
        if (st.size())R[i]=st.top()-1;
        else R[i]=n;
        st.push(i);
    }
    vector<ST> dp;
    for (int i=0;i<=k+5;i++)dp.push_back(ST(n));
    dp[0].upd(1,0,n,0,0,0);
    for (int i=1;i<=n;i++)
    {
        int l=L[i]-1;
        int r=i-1;
        int u=i;
        int v=R[i];
        //cerr<<L[i]<<" "<<R[i]<<endl;
        for (int j=0;j<k;j++)
        {
            int val=dp[j].get(1,0,n,l,r);
            dp[j+1].upd(1,0,n,u,v,val+a[i]);
        }
    }    
    cout<<dp[k].get(1,0,n,n,n);
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int32_t main()':
blocks.cpp:25:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:77:5: note: in expansion of macro 'file'
   77 |     file();
      |     ^~~~
blocks.cpp:25:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:77:5: note: in expansion of macro 'file'
   77 |     file();
      |     ^~~~

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