Submission #171884

#	Time	Username	Problem	Language	Result	Execution time	Memory
171884		Swan	K blocks (IZhO14_blocks)	C++14	0 / 100	1086 ms	1656 KiB

blocks

#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 fst_mx[maxn];
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;
    }

    brute();
    return 0;
}
/*
5 4
1 2 3 4 5
*/

Compilation message (stderr)

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

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