Submission #47045

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
47045	2018-04-27 03:36:31	wzy	K blocks (IZhO14_blocks)	C++11	100 / 100	455 ms	122864 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 <bits/stdc++.h>
using namespace std;
int n , k , dp[100005][105] , v[100005] , opt[100005][105] , pointer[105];
stack< pair<int,int> > s[105];
int main(){
  scanf("%d%d" , &n , &k);
  for(int i = 1 ; i<=n ;i ++) scanf("%d" , &v[i]);
  for(int i = 0 ; i  <= n; i ++)
    for(int j = 0 ; j <= k ; j++) opt[i][j] = 1000000009 , pointer[j] = 0 , dp[i][j] = 0;
  for(int j = 1 ; j <= k ; j++)
    for(int i = j ; i <= n; i++){
      if(j == 1){
        dp[i][j] = max(dp[i-1][j] , v[i]);
      }   
      else{
        int currminimal = dp[i-1][j-1];
        while(s[j].size() && s[j].top().second <= v[i]){
          currminimal = min(currminimal , s[j].top().first);
          s[j].pop();
          pointer[j]--;
        }
        dp[i][j] = min(currminimal + v[i] , opt[pointer[j]][j]);
        s[j].push(pair<int,int>(currminimal, v[i]));
        opt[pointer[j] + 1][j] = min(opt[pointer[j]][j] , currminimal + v[i]);
        pointer[j]++;
      }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:14:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int j = 1 ; j <= k ; j++)
  ^~~
blocks.cpp:32:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   printf("%d\n" , dp[n][k]);
   ^~~~~~
blocks.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &k);
  ~~~~~^~~~~~~~~~~~~~~~~~
blocks.cpp:11:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i<=n ;i ++) scanf("%d" , &v[i]);
                              ~~~~~^~~~~~~~~~~~~~

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