Submission #393008

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
393008	2021-04-22 14:10:07	patrikpavic2	K blocks (IZhO14_blocks)	C++17	100 / 100	396 ms	43080 KiB

blocks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <stack>
#include <cstring>
#define X first
#define Y second
using namespace std;
const int N = 1e5 + 500;
const int K = 105;
const int INF = 0x3f3f3f3f;
int dp[N][K], n, k, A[N];
stack < int > S, ja, sve;
int main(){
  memset(dp, INF, sizeof(dp)); dp[0][0] = 0;
  scanf("%d%d", &n, &k);
  for(int i = 1;i <= n;i++)
    scanf("%d", A + i);
  for(int j = 1;j <= k;j++){
    S.push(0); ja.push(dp[0][j - 1]); sve.push(dp[0][j - 1]);
    for(int i = 1;i <= n;i++){
      int bst = dp[i - 1][j - 1];
      while(!S.empty() && S.top() <= A[i]){
        bst = min(bst, ja.top()); 
        S.pop(); ja.pop(); sve.pop();
      }
      S.push(A[i]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47