Submission #171881

#	Time	Username	Problem	Language	Result	Execution time	Memory
171881		Swan	UFO (IZhO14_ufo)	C++14	0 / 100	2058 ms	16960 KiB

ufo

#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;

const int maxn = 100004;

vector<int> v;
int dp[102][maxn];
int f[102][maxn];
int tree[102][4*maxn];

int fst_mx[maxn];

void build(int num,int v,int l,int r){
    if(l == r && num == 1){
        tree[num][v] = dp[num][l];
        return;
    }
    if(l == r){
        tree[num][v] = 1e9;
        return;
    }
    int m = (l+r)/2;
    build(num,v*2,l,m);
    build(num,v*2+1,m+1,r);
    tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}

int get_min(int num,int v,int l,int r,int le,int re){
    if(l>=le && r <=re)return tree[num][v];
    if(l > re || r < le)return 1e9;
    int m = (l+r)/2;
    int a = get_min(num,v*2,l,m,le,re);
    int b = get_min(num,v*2+1,m+1,r,le,re);
    return min(a,b);
}

void set_pos(int num,int v,int l,int r,int need){
    if(l == r){
        tree[num][v] = dp[num][l];
        return;
    }
    int m = (l+r)/2;
    if(need<=m)set_pos(num,v*2,l,m,need);
    else set_pos(num,v*2+1,m+1,r,need);
    tree[num][v] = min(tree[num][v*2],tree[num][v*2+1]);
}

int n,k;

void brute(){
    for(int cnt(2);cnt<=k;cnt++){
        for(int i(cnt);i<=n;i++){
            f[cnt][i] = 1e9;
            int now = v[i];
            for(int to(i-1);to>=0;to--){
                f[cnt][i] = min(f[cnt][i],now+f[cnt-1][to]);
            }
        }
    }
    cout << f[k][n] << endl;
}

main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    v.push_back(0);
    int now = 0;
    dp[1][0] = f[1][0] = 1e9;
    for(int i(1); i <= n;i++){
        int x; cin >> x;
        now = max(now,x);
        f[1][i] = dp[1][i] = now;
        v.push_back(x);
        fst_mx[i] = -1;
    }
    stack<int> s;
    for(int i(0); i < n;i++){
        while(s.size() && (v[s.top()] < v[i]))s.pop();
        if(s.size())fst_mx[i] = s.top();
        s.push(i);
    }
    for(int i(1);i<=k;i++)build(i,1,0,n);
    //cout << get_min(2,1,0,n,0,3) << endl;
    for(int cnt(2);cnt<=k;cnt++){
        for(int i(cnt);i<=n;i++){
            int now = 1e9;
            if(dp[cnt-1][i-1]!=1e9){
                now = dp[cnt-1][i-1]+v[i];
            }
            int nxt = fst_mx[i];
            int to = 0;
            //cout << now << endl;
            if(nxt!=-1){
                now = min(now,dp[cnt][nxt]);
                to = nxt+1;
            }
            //cout << now << endl;
            if(to!=i)now = min(now,v[i]+get_min(cnt-1,1,0,n,to,i-1));
            //cout << i << ' ' << v[i] << ' ' << to << ' ' << i-1 << ' ' << get_min(cnt-1,1,0,n,to,i-1) << endl;
            dp[cnt][i] = now;
            //cout << cnt << ' ' << i << ' ' << now << ' ' << to << ' ' << i << endl;
            set_pos(cnt,1,0,n,i);
        }
    }
    brute();
    return 0;
}
/*
5 4
1 2 3 4 5
*/

Compilation message (stderr)

ufo.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 0 / 100