oj.uz

Submission #714416

# Submission time Handle Problem Language Result Execution time Memory
714416 2023-03-24T10:42:08 Z Quan2003 K blocks (IZhO14_blocks) C++17
0 / 100
 180 ms 262144 KB 
#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int M = 5e2 + 10;
const long long INF = 1e17; 
long long n,m,comp,k,s,t,q;
char g[M + 1][M + 1]; 
int block[N + 1]; 
long long dp[N + 1][M + 1];
long long a[N + 1]; 
int fa[N + 1]; 
int timer = 1;  
int main(){
      cin >> n >> k;
      for(int i = 1; i <= n; i++) cin >> a[i]; 
      memset(dp,0x3f3f3f3f,sizeof(dp));
      dp[0][1] = 0; 
      for(int i = 1; i <= n; i++) dp[i][1] = max(dp[i - 1][1], a[i]); 
      for(int i = 2; i <= k; i++){
           stack<pair<long long,int>>stk;
           for(int j = i; j <= n; j++){
               long long mn = dp[j - 1][i - 1];
               while(stk.size() && a[stk.top().second] <= a[j]){
                     mn = min(mn, stk.top().first);
                     stk.pop(); 
               }
               dp[j][i] = min(dp[stk.size() ? stk.top().second : 0][i], mn + a[j]);
               stk.push({mn,j}); 
           }
      }
      cout << dp[n][k] << endl; 
      return 0; 
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -