Submission #714413

#	Time	Username	Problem	Language	Result	Execution time	Memory
714413		Quan2003	K blocks (IZhO14_blocks)	C++17	0 / 100	103 ms	262144 KiB

blocks

#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 (stderr)

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47