Submission #1270642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270642		luattapcode	K blocks (IZhO14_blocks)	C++20	100 / 100	152 ms	85088 KiB

blocks

/*The best way to get something done is to begin*/
#include     <bits/stdc++.h>
#define     ll long long
#define     int long long
#define     fr(i,a,b) for(int i=a;i<=b;i++)
#define     frd(i,a,b) for(int i=a;i>=b;i--)
#define     pb push_back
#define     fi first
#define     se second
#define     el '\n'
using namespace std;
template <class X, class Y> bool minimize(X &x, const Y &y) {if (x > y) {x = y;return true;} else return false;}
template <class X, class Y> bool maximize(X &x, const Y &y) {if (x < y) {x = y;return true;} else return false;}
/* Author: Huynh Quoc Luat */
/*Khai Bao*/
const long long inf=1e18;
const int oo=1e9;
const int LO=21;
const int CH=27;
const int N=2e5+5;
const int sm=1e9+7;
int n,k;
int a[N];
//void add(int &x,const int &y){x+=y;if(x>=sm)x-=sm;}
//void sub(int &x,const int &y){x-=y;if(x<0)x+=sm;}

void read()
{
    cin >> n >> k;
    fr(i,1,n) cin >> a[i];
}   

namespace sub1
{
    int t[4*N];
    void build(int id,int l,int r){
        if(l==r){
            t[id]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(2*id,l,mid);
        build(2*id+1,mid+1,r);
        t[id]=max(t[2*id],t[2*id+1]);
    }
    int get(int id,int l,int r,int u,int v){
        if(u>r or v<l) return -inf;
        if(u<=l and v>=r) return t[id];
        int mid=(l+r)>>1;
        return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
    }
    const int K=509;
    vector <int> dp[K];
    void process()
    {
        build(1,1,n);
        // cout << get(1,1,n,1,4) << el;
        fr(i,0,k+5) dp[i].assign(n+5,inf);
        dp[0][0]=0;
        dp[1][1]=a[1];
        fr(j,1,k){
            fr(i,2,n){
                fr(pos,1,i){
                    minimize(dp[j][i],dp[j-1][pos-1]+get(1,1,n,pos,i));
                }
            }
        }
        cout << dp[k][n];
        cout << el;
        fr(i,1,k){
            fr(j,1,n) cout << dp[i][j] << " ";
            cout << el;
        }
    }
}

namespace sub2
{
    const int K=509;
    vector <int> dp[K];
    stack <pair <int,int>> st;
    void process(){
        fr(i,0,k+5) dp[i].assign(n+5,inf);
        dp[0][0]=0;
        dp[1][1]=a[1];
        fr(i,2,n) dp[1][i]=max(dp[1][i-1],a[i]);
        fr(j,2,k){
            while(!st.empty()) st.pop();
            fr(i,j,n){
                int cur=dp[j-1][i-1];
                while(!st.empty() and a[st.top().fi] <= a[i]){
                    minimize(cur,st.top().se);
                    st.pop();
                } 
                int tmp=st.empty() ? inf :dp[j][st.top().fi];
                dp[j][i]=min(cur+a[i],tmp);
                st.push({i,cur});
            }
        }
        cout << dp[k][n];
        // cout << el;
        // fr(i,1,k){
        //     fr(j,1,n) cout << dp[i][j] << " ";
        //     cout << el;
        // }
    }
}
void time()    {cerr<< endl<<"Luattapcode: "<<clock()<<"ms"<<endl;}
main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    #define TASK "qn"
    if(fopen(TASK".INP","r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    int mtt=0;
    int test=1;
    if(mtt) cin>>test;
    while(test--)
    {
        read();
        sub2 ::process();
    }
    time();
    return 0;
}

Compilation message (stderr)

blocks.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main()
      | ^~~~
blocks.cpp: In function 'int main()':
blocks.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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