oj.uz

Submission #38070

# Submission time Handle Problem Language Result Execution time Memory
38070 2017-12-31T17:07:00 Z nickyrio K blocks (IZhO14_blocks) C++14
0 / 100
 56 ms 69272 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 100100
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "Test"
using namespace std;

template<class X, class Y> inline void Max(X &x, Y y) { x = x > y ? x : y; }
template<class X, class Y> inline void Min(X &x, Y y) { x = x < y ? x : y; }
/*
dp[i][j] = min(dp[i - 1][k] + RMQ[k + 1][j]);

*/

int n, k, a[N];
vector<int> e[N * 10];
int dp[111][N];

stack<int> st;

int main() {
    IO;
    scanf("%d %d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
    int mx = -1;
    FOR(i, 1, n) Max(mx, a[i]), dp[1][i] = mx; 
    FOR(j, 2, k) {
        while (!st.empty()) st.pop();
        st.push(j - 1);
        FOR(i, j, n) {
            int best = 1e9;
            while (!st.empty() && a[st.top()] <= a[i]) {
                if (st.top() != j - 1) Min(best, dp[j][st.top()] + a[i] - a[st.top()]);
                st.pop();
            }
            if (!st.empty() && st.top() != j - 1) {
                Min(best, dp[j][st.top()]);
                Min(best, dp[j - 1][st.top()] + a[i]);
            }
            else Min(best, dp[j - 1][j - 1] + a[i]);
            dp[j][i] = best;
            //cerr << j << ' ' << i << ' ' << best << endl;
            st.push(i);
        }
    }
    printf("%d", dp[k][n]);
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:32:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
                           ^
blocks.cpp:33:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 69272 KB Output is correct
2 Correct 19 ms 69272 KB Output is correct
3 Correct 19 ms 69272 KB Output is correct
4 Incorrect 56 ms 69272 KB Output isn't correct
5 Halted 0 ms 0 KB -