oj.uz

Submission #1049234

# Submission time Handle Problem Language Result Execution time Memory
1049234 2024-08-08T15:18:09 Z vjudge1 Bikeparking (EGOI24_bikeparking) C++17
0 / 100
 0 ms 348 KB 
#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];
	int c = A[0];
	bool b = 1;
	for(int i = 0;i < n;i++){
		if(A[i] != c || B[i] != c){
			b = 0;
			break;
		}
	}
	if(b){ // Sub 2 :D
		cout<<max(1ll, c * (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
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -