oj.uz

Submission #761565

# Submission time Handle Problem Language Result Execution time Memory
761565 2023-06-20T03:47:34 Z KN200711 Skyline (IZhO11_skyline) C++14
100 / 100
 108 ms 109360 KB 
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

const int MX = 301;
int dp[MX][MX][MX];
int N;
int arr[MX];

int solve(int idx, int p1, int p2) {
	if(idx == N) {
		return min(p1, p2) * 5 + (max(p1, p2) - min(p1, p2)) * 3;
	}
	if(dp[idx][p1][p2] != -1) return dp[idx][p1][p2];
	int mn = 1e9;
	
	// solve kalo ambil 2
	if(p1 > 0 && p2 > 0) mn = min(mn, solve(idx, p1 - 1, p2 - 1) + 5);
	
	// solve kalo ambil 3
	int sum = 0;
	int t3 = min(arr[idx], min(p1, p2));
	sum += 7 * t3;
	// solve p2 nya
	int t2 = min(p1 - t3, p2 - t3);
	sum += 5 * t2;
	
	int t1 = p2 - t3 - t2;
	sum += 3 * t1;
	
	mn = min(mn, solve(idx + 1, arr[idx] - t3, p1 - t2 - t3) + sum);
	dp[idx][p1][p2] = mn;
	return mn;
}

int main() {
	for(int i=0;i<MX;i++) {
		for(int k=0;k<MX;k++) {
			for(int c=0;c<MX;c++) {
				dp[i][k][c] = -1;
			}
		}
	}
	scanf("%d", &N);
	for(int i=0;i<N;i++) scanf("%d", &arr[i]);
	
	if(N == 1) printf("%d\n", arr[0] * 3);
	else if(N == 2) printf("%d\n", min(arr[0], arr[1]) * 5 + (max(arr[0], arr[1]) - min(arr[0], arr[1])) * 3);
	else printf("%d\n", solve(2, arr[1], arr[0]));
	
	return 0;
}

Compilation message

skyline.cpp: In function 'int main()':
skyline.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
skyline.cpp:47:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  for(int i=0;i<N;i++) scanf("%d", &arr[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 106956 KB Output is correct
2 Correct 35 ms 106928 KB Output is correct
3 Correct 35 ms 106964 KB Output is correct
4 Correct 35 ms 106968 KB Output is correct
5 Correct 35 ms 106940 KB Output is correct
6 Correct 35 ms 107004 KB Output is correct
7 Correct 35 ms 106956 KB Output is correct
8 Correct 35 ms 106996 KB Output is correct
9 Correct 35 ms 106964 KB Output is correct
10 Correct 36 ms 107020 KB Output is correct
11 Correct 40 ms 107348 KB Output is correct
12 Correct 38 ms 107116 KB Output is correct
13 Correct 41 ms 107452 KB Output is correct
14 Correct 45 ms 107636 KB Output is correct
15 Correct 84 ms 108824 KB Output is correct
16 Correct 81 ms 108588 KB Output is correct
17 Correct 107 ms 109360 KB Output is correct
18 Correct 108 ms 109260 KB Output is correct
19 Correct 100 ms 109052 KB Output is correct
20 Correct 108 ms 109288 KB Output is correct