Submission #1049232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049232		vjudge1	Bikeparking (EGOI24_bikeparking)	C++17	40 / 100	145 ms	33624 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int N = 200;
const int X = N * N;
const int K = 500;
const int MOD = 1e9 + 7;

const int LOG = 21;
const int INF = 1e17;


int dp[N][X];

signed main(){ios::sync_with_stdio(false);cin.tie(0);	
	int n;
	cin>>n;
	int A[n], B[n];
	for(int i = 0;i  <n;i++)cin>>A[i];
	for(int i = 0;i < n;i++)cin>>B[i];
	if(n > 100){ // Sub 2 :D
		cout<<max(0ll, A[0] * (n - 2));
		return 0;
	}
	int sum = 0;
	for(int i = 0;i  <n;i++)sum += A[i] - B[i];
	for(int i = n - 1;i >= 0;i--){
		if(A[i] <= sum)sum -= A[i], A[i] = 0;
		else{
			A[i] -= sum;
			break;
		}
	}
	for(int i = 0;i <= n;i++){
		for(int j = 0;j < X;j++)dp[i][j] = -INF;
	}
	dp[0][0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < X;j++){
			for(int k = 0;k <= min(A[i] + j, B[i]);k++){
				dp[i + 1][A[i] + j - k] = max(dp[i + 1][A[i] + j - k], dp[i][j] + min(j, k));
			}
		}
	}
	int ans = -INF;
	for(int i = 0;i < X;i++)ans = max(ans, dp[n][i] - i);
	cout<<ans;
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 9
• Subtask 3: 0 / 19
• Subtask 4: 24 / 24
• Subtask 5: 0 / 32