Submission #1285286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285286		Faisal_Saqib	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	270 ms	4776 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100100;
ll a[N];
ll dp[N][3];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i][0]=1e14;
    }
    // dp[0][1]=1e14;
    for(int j=1;j<=k;j++)
    {
        int p=j%2;
        for(int i=0;i<=n;i++)dp[i][p]=1e14;
        vector<int> st_mx,st_dp;
        vector<ll> ans;
        st_mx.push_back(0);
        st_dp.push_back(0);
        ans.push_back(dp[0][p]);
        for(int i=1;i<=n;i++)
        {
            // dp[i][p]=min( dp[i'][1-p] + max(a[i'+1 , i'+2 , .. , i]) ) 'i<i
            while(st_mx.size()>1 and a[st_mx.back()]<=a[i])
            {
                st_mx.pop_back();
                ans.pop_back();
            }
            // dp[i][p]=;
            auto it=lower_bound(begin(st_dp),end(st_dp),st_mx.back());
            // cout<<"BACK "<<st_mx.back()<<endl;;
            ll etx=1e14;
            if(it!=end(st_dp))
            {
                etx=dp[*it][1-p];
                // spl=*it;
            }
            st_mx.push_back(i);
            ans.push_back(min(ans.back(),etx+a[i]));
            // cout<<"Split for "<<i<<' '<<p<<' '<<' '<<etx<<' '<<a[i]<<' '<<ans.back()<<endl;;
            dp[i][p]=ans.back();
            // cout<<"dp[ "<<i<<" ][ "<<j<<" ] = "<<dp[i][p]<<endl;
            while(st_dp.size()>0 and dp[st_dp.back()][1-p]>=dp[i][1-p])
            {
                st_dp.pop_back();
            }
            st_dp.push_back(i);
            // cout<<"st_dp: ";
            // for(auto x:st_dp)cout<<x<<' ';
            // cout<<endl;
            // cout<<"st_dp: ";
            // for(auto x:st_dp)cout<<dp[x][1-p]<<' ';
            // cout<<endl;
        }
    }
    cout<<dp[n][k%2]<<endl;
}

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