Submission #761565

#	Time	Username	Problem	Language	Result	Execution time	Memory
761565		KN200711	Skyline (IZhO11_skyline)	C++14	100 / 100	108 ms	109360 KiB

skyline

# 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 (stderr)

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 / 100