oj.uz

Submission #294669

# Submission time Handle Problem Language Result Execution time Memory
294669 2020-09-09T08:15:44 Z phathnv K blocks (IZhO14_blocks) C++11
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int K = 101;
const int INF = 1e9;

int n, k, h[N];

int top, dp[K][N];
ii St[N];

int main(){
    freopen("blocks.in", "r", stdin);
    freopen("blocks.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> h[i];

    dp[1][1] = h[1];
    for(int i = 2; i <= n; i++)
        dp[1][i] = max(dp[1][i - 1], h[i]);
    for(int c = 2; c <= k; c++){
        top = 0;
        h[c - 1] = INF;
        dp[c][c - 1] = INF;
        St[++top] = mp(c - 1, dp[c - 1][c - 1]);
        for(int i = c; i <= n; i++){
            while (h[i] >= h[St[top].X]){
                St[top - 1].Y = min(St[top - 1].Y, St[top].Y);
                top--;
            }
            dp[c][i] = min(dp[c][St[top].X], St[top].Y + h[i]);
            St[++top] = mp(i, dp[c - 1][i]);
        }
    }

    cout << dp[k][n];

    return 0;
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     freopen("blocks.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     freopen("blocks.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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