Submission #1200336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200336		zNatsumi	Stove (JOI18_stove)	C++20	50 / 100	271 ms	327680 KiB

stove

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 5e3 + 5;
const int INF = 1e18;

int n, k, t[N], dp[N][N][2];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> t[i];

  for(int i = 0; i <= n; i++)
    for(int j = 0; j <= k; j++) dp[i][j][0] = dp[i][j][1] = INF;

  dp[0][0][1] = 0;
  for(int i = 0; i < n; i++)
    for(int j = 0; j <= k; j++){
//      cerr << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << "\n";
      if(dp[i][j][1] != INF){
        dp[i + 1][j + 1][0] = min(dp[i + 1][j + 1][0], dp[i][j][1] - t[i + 1]);
        dp[i + 1][j + 1][1] = min(dp[i + 1][j + 1][1], dp[i][j][1] + 1);
      }
      if(dp[i][j][0] != INF){
        dp[i + 1][j][0] = min(dp[i + 1][j][0], dp[i][j][0]);
        dp[i + 1][j][1] = min(dp[i + 1][j][1], dp[i][j][0] + t[i + 1] + 1);
      }
    }
  cout << dp[n][k][1] << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50