Submission #1266025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266025		rayan_bd	K blocks (IZhO14_blocks)	C++20	Compilation error	0 ms	0 KiB

blocks

t.tie(nullptr);

    int N, K;
    cin >> N >> K;

    for(int i = 0; i <= N; ++i){
        for(int j = 0; j <= K; ++j){
            dp[i][j] = INF;
        }
    }

    for(int i = 1; i <= N; ++i) cin >> a[i];

    for(int i = 0; i <= N; ++i) dp[i][0] = 0;

    for(int i = 1, mx = 1; i <= N; ++i){
        mx = max(mx, a[i]);
        dp[i][1] = mx;
    }

    for(int k = 2; k <= K; ++k){
        stack<int> st;
        for(int i = 1; i <= N; ++i){
            mn[i] = INF;
            while(st.size() && a[st.top()] <= a[i]){
                dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[i]);
                mn[i] = min({mn[i], dp[st.top()][k - 1], mn[st.top()]});
                dp[i][k] = min(dp[i][k], mn[i] + a[i]);
                st.pop();
            }
            if(st.size()){
                dp[i][k] =  min(dp[i][k], dp[st.top()][k]); // extend
                dp[i][k] = min(dp[i][k], dp[st.top()][k - 1] + a[i]); // from st.top() + 1, to i
                dp[i][k] = min(dp[i][k], dp[st.top() - 1][k - 1] + a[st.top()]); // (st.top() -> i)
             //   dp[i][k] = min(dp[i][k], mn[st.top()] + a[i]); mn[i] not equal to dp[st.top()][k - 1]
            }
            dp[i][k] = min(dp[i][k], dp[i - 1][k - 1] + a[i]);
            st.push(i);
        }
    }

    cout << dp[N][K] << "\n";

    return 0;
}

Compilation message (stderr)

blocks.cpp:1:1: error: 't' does not name a type
    1 | t.tie(nullptr);
      | ^
blocks.cpp:4:5: error: 'cin' does not name a type
    4 |     cin >> N >> K;
      |     ^~~
blocks.cpp:6:5: error: expected unqualified-id before 'for'
    6 |     for(int i = 0; i <= N; ++i){
      |     ^~~
blocks.cpp:6:20: error: 'i' does not name a type
    6 |     for(int i = 0; i <= N; ++i){
      |                    ^
blocks.cpp:6:28: error: expected unqualified-id before '++' token
    6 |     for(int i = 0; i <= N; ++i){
      |                            ^~
blocks.cpp:12:5: error: expected unqualified-id before 'for'
   12 |     for(int i = 1; i <= N; ++i) cin >> a[i];
      |     ^~~
blocks.cpp:12:20: error: 'i' does not name a type
   12 |     for(int i = 1; i <= N; ++i) cin >> a[i];
      |                    ^
blocks.cpp:12:28: error: expected unqualified-id before '++' token
   12 |     for(int i = 1; i <= N; ++i) cin >> a[i];
      |                            ^~
blocks.cpp:14:5: error: expected unqualified-id before 'for'
   14 |     for(int i = 0; i <= N; ++i) dp[i][0] = 0;
      |     ^~~
blocks.cpp:14:20: error: 'i' does not name a type
   14 |     for(int i = 0; i <= N; ++i) dp[i][0] = 0;
      |                    ^
blocks.cpp:14:28: error: expected unqualified-id before '++' token
   14 |     for(int i = 0; i <= N; ++i) dp[i][0] = 0;
      |                            ^~
blocks.cpp:16:5: error: expected unqualified-id before 'for'
   16 |     for(int i = 1, mx = 1; i <= N; ++i){
      |     ^~~
blocks.cpp:16:28: error: 'i' does not name a type
   16 |     for(int i = 1, mx = 1; i <= N; ++i){
      |                            ^
blocks.cpp:16:36: error: expected unqualified-id before '++' token
   16 |     for(int i = 1, mx = 1; i <= N; ++i){
      |                                    ^~
blocks.cpp:21:5: error: expected unqualified-id before 'for'
   21 |     for(int k = 2; k <= K; ++k){
      |     ^~~
blocks.cpp:21:20: error: 'k' does not name a type
   21 |     for(int k = 2; k <= K; ++k){
      |                    ^
blocks.cpp:21:28: error: expected unqualified-id before '++' token
   21 |     for(int k = 2; k <= K; ++k){
      |                            ^~
blocks.cpp:42:5: error: 'cout' does not name a type
   42 |     cout << dp[N][K] << "\n";
      |     ^~~~
blocks.cpp:44:5: error: expected unqualified-id before 'return'
   44 |     return 0;
      |     ^~~~~~
blocks.cpp:45:1: error: expected declaration before '}' token
   45 | }
      | ^