Submission #1270629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270629		luattapcode	K blocks (IZhO14_blocks)	C++20	53 / 100	1096 ms	3144 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;
        // }
    }
}
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();
        sub1::process();
    }
    time();
    return 0;
}

Compilation message (stderr)

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

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