Submission #671950

#	Time	Username	Problem	Language	Result	Execution time	Memory
671950		smartmonky	K blocks (IZhO14_blocks)	C++14	100 / 100	176 ms	42716 KiB

blocks

 #include <bits/stdc++.h>
     
   #define ff first
   #define ss second
   #define pb push_back
   #define all(x) x.begin(), x.end()
   #define rall(x) x.rbegin(), x.rend()
   using namespace std;
    
   const int N = 1e5 + 50;
   int dp[105][N];
   main(){
   	ios_base::sync_with_stdio(0);
   	cin.tie(0);
   	cout.tie(0);
   	memset(dp, 0x3f3f, sizeof(dp));
   	int n, k;
   	cin >> n >> k;
   	vector <int> v(n + 1);
   	for(int i = 1; i <= n; i++){
   		cin >> v[i];
   	}
   	dp[1][0] = -1e9;
   	for(int i = 1; i <= n; i++)dp[1][i] = max(v[i], dp[1][i - 1]);
   	for(int i = 2; i <= k; i++){
   		deque <pair <int,int> > d;
   		for(int j = i; j <= n; j++){
   			int prev = dp[i - 1][j - 1];
   			while(!d.empty() && d.front().ff <= v[j]){
   				prev = min(d.front().ss, prev);
   				d.pop_front();
   			}
   			if(d.empty() || prev + v[j] < d.front().ff + d.front().ss){
   				d.push_front({v[j], prev});
   			}
   			dp[i][j] = d.front().ff + d.front().ss;
   		}
   	}
   	cout << dp[k][n];
   }

Compilation message (stderr)

blocks.cpp:12:4: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 |    main(){
      |    ^~~~

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