oj.uz

답안 #465281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465281 2021-08-15T13:30:41 Z dattranxxx Stove (JOI18_stove) C++11
50 / 100
 149 ms 198864 KB 
/*
 * 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;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98116 KB Output is correct
2 Correct 42 ms 98100 KB Output is correct
3 Correct 44 ms 98132 KB Output is correct
4 Correct 45 ms 98140 KB Output is correct
5 Correct 45 ms 98156 KB Output is correct
6 Correct 43 ms 98152 KB Output is correct
7 Correct 44 ms 98148 KB Output is correct
8 Correct 50 ms 98144 KB Output is correct
9 Correct 44 ms 98196 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98116 KB Output is correct
2 Correct 42 ms 98100 KB Output is correct
3 Correct 44 ms 98132 KB Output is correct
4 Correct 45 ms 98140 KB Output is correct
5 Correct 45 ms 98156 KB Output is correct
6 Correct 43 ms 98152 KB Output is correct
7 Correct 44 ms 98148 KB Output is correct
8 Correct 50 ms 98144 KB Output is correct
9 Correct 44 ms 98196 KB Output is correct
10 Correct 46 ms 98180 KB Output is correct
11 Correct 45 ms 98192 KB Output is correct
12 Correct 49 ms 98100 KB Output is correct
13 Correct 53 ms 98136 KB Output is correct
14 Correct 57 ms 98116 KB Output is correct
15 Correct 56 ms 98124 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98116 KB Output is correct
2 Correct 42 ms 98100 KB Output is correct
3 Correct 44 ms 98132 KB Output is correct
4 Correct 45 ms 98140 KB Output is correct
5 Correct 45 ms 98156 KB Output is correct
6 Correct 43 ms 98152 KB Output is correct
7 Correct 44 ms 98148 KB Output is correct
8 Correct 50 ms 98144 KB Output is correct
9 Correct 44 ms 98196 KB Output is correct
10 Correct 46 ms 98180 KB Output is correct
11 Correct 45 ms 98192 KB Output is correct
12 Correct 49 ms 98100 KB Output is correct
13 Correct 53 ms 98136 KB Output is correct
14 Correct 57 ms 98116 KB Output is correct
15 Correct 56 ms 98124 KB Output is correct
16 Runtime error 149 ms 198864 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -