oj.uz

Submission #714413

# Submission time Handle Problem Language Result Execution time Memory
714413 2023-03-24T10:41:05 Z Quan2003 K blocks (IZhO14_blocks) C++17
0 / 100
 103 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(){
      scanf("%d%d",&n,&k);
      for(int i = 1; i <= n; i++) scanf("%d",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}); 
           }
      }
      printf("%lld\n",dp[n][k]); 
      return 0; 
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:18:15: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   18 |       scanf("%d%d",&n,&k);
      |              ~^    ~~
      |               |    |
      |               int* long long int*
      |              %lld
blocks.cpp:18:17: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   18 |       scanf("%d%d",&n,&k);
      |                ~^     ~~
      |                 |     |
      |                 int*  long long int*
      |                %lld
blocks.cpp:19:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   19 |       for(int i = 1; i <= n; i++) scanf("%d",a + i);
      |                                          ~^  ~~~~~
      |                                           |    |
      |                                           int* long long int*
      |                                          %lld
blocks.cpp:18:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |       scanf("%d%d",&n,&k);
      |       ~~~~~^~~~~~~~~~~~~~
blocks.cpp:19:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |       for(int i = 1; i <= n; i++) scanf("%d",a + i);
      |                                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 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 103 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 101 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 101 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -