oj.uz

Submission #785701

# Submission time Handle Problem Language Result Execution time Memory
785701 2023-07-17T13:23:09 Z mdub K blocks (IZhO14_blocks) C++14
0 / 100
 1 ms 300 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -