제출 #465281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465281		dattranxxx	Stove (JOI18_stove)	C++11	50 / 100	149 ms	198864 KiB

stove

/*
 * Author :  shora
 */
#include <bits/stdc++.h>
#define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl;
using namespace std;
using ll = long long;
const int oo = 1e9;
const int N = 5000;
int a[N+1];
int n, k;
int dp[N+1][N+1];
int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
  	cin >> a[i];
  // dp[j][i] = a[i] + min(dp[j-1][u-1] - a[u]) + 1 : u <= i
  // dp[j][i] = a[i] + g[j-1] + 1 voi g[i] = min(dp[i][p-1] + a[p]) 
  // dp[i] la mot day tang 
  // a[i] la mot day tang
	memset(dp, 0x3f, sizeof(dp));
	int res = oo;
	for (int i = 0; i <= k; ++i) dp[i][0] = 0;
  for (int i = 1; i <= k; ++i) {
  	int mn = oo;
  	for (int j = 1; j <= n; ++j) {
  		mn = min(mn, dp[i-1][j-1] - a[j]);
  		dp[i][j] = a[j] + mn + 1;
		}
	}
	cout << dp[k][n];
  
  
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

stove.cpp: In function 'int main()':
stove.cpp:23:6: warning: unused variable 'res' [-Wunused-variable]
   23 |  int res = oo;
      |      ^~~

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