Submission #785701

#	Time	Username	Problem	Language	Result	Execution time	Memory
785701		mdub	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	300 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

int main () {
  int n, k; cin >> n >> k;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<pair<long long, long long>>> dp(n, vector<pair<long long, long long>>(k, {1e18, 0}));
  dp[0][0] = {a[0], a[0]};
  for (int j = 0; j < k; j++) {
    for (int i = 0; i < n-1; i++) {
      long long temp = dp[i][j].first + max((long long)(0), a[i + 1] - a[i]);
      if (temp < dp[i + 1][j].first) {
	dp[i + 1][j].first = temp;
	dp[i + 1][j].second = max(a[i + 1], dp[i][j].second);  
      }
      else if (temp == dp[i + 1][j].first) {
	dp[i + 1][j].second = max({a[i + 1], dp[i][j].second, dp[i + 1][j].second});
      }
      if (j < k - 1) {
	if (dp[i][j].first + a[i + 1] < dp[i + 1][j + 1].first) {
	  dp[i + 1][j + 1].first = dp[i][j].first + a[i + 1];
	  dp[i + 1][j + 1].second = a[i + 1];
	}
	else if (dp[i][j].first + a[i + 1] == dp[i + 1][j + 1].first) {
	  dp[i + 1][j + 1].second = max(a[i + 1], dp[i + 1][j + 1].second);
	}
      }
	  
    }
  }
  cout << dp[n-1][k-1].first << '\n';
  
}

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