oj.uz

Submission #171884

# Submission time Handle Problem Language Result Execution time Memory
171884 2019-12-30T14:52:14 Z Swan K blocks (IZhO14_blocks) C++14
0 / 100
 1000 ms 1656 KB 
#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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 1656 KB Time limit exceeded
2 Halted 0 ms 0 KB -