Submission #47045

#	Time	Username	Problem	Language	Result	Execution time	Memory
47045		wzy	K blocks (IZhO14_blocks)	C++11	100 / 100	455 ms	122864 KiB

blocks

#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]++;
			}
		}
		printf("%d\n" , dp[n][k]);

}

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