Submission #1336760

#TimeUsernameProblemLanguageResultExecution timeMemory
1336760edl0231Bikeparking (EGOI24_bikeparking)C++20
40 / 100
1095 ms3888 KiB
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> x;
vector<int> y;
bool check(int c)
{
    vector<int> v = y;
    for (int i = 0; i < N; i++)
    {
        if (c > v[i]) {c -= v[i]; v[i] = 0; continue;}
        v[i] -= c;
        break;
    }
    int sum_x = 0, sum_y = 0;
    for (int i = 0; i < N; i++)
    {
        sum_x += x[i], sum_y += v[i];
        if (sum_x < sum_y) return false;
    }
    return true;
}
int get_ans(int c)
{
    int temp = c;
    vector<int> v = y;
    for (int i = 0; i < N; i++)
    {
        if (c > v[i]) {c -= v[i]; v[i] = 0; continue;}
        v[i] -= c;
        break;
    }
    int sum_x = 0, sum_y = 0;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        sum_x += x[i], sum_y += v[i];
        ans += min((sum_x - x[i]) - (sum_y - v[i]), v[i]);
    }
    return ans - temp;
}
int main()
{
    cin >> N;
    x.resize(N), y.resize(N);
    int mx1 = 0, mx2 = 0;
    for (int i = 0; i < N; i++) cin >> x[i], mx1 = max(mx1, x[i]);
    for (int i = 0; i < N; i++) cin >> y[i], mx2 = max(mx2, y[i]);
    if (mx1 <= 100 && mx2 <= 100 && N <= 100)
    {
        int r = 0;
        for (int i = 0; i < N; i++) r += y[i];
        int ans = -10000000;
        for (int i = 0; i <= r; i++)
        {
            if (check(i)) {ans = max(ans, get_ans(i));}// cout << i << " : " << get_ans(i) << ' ';}
        }
        cout << ans << '\n';
        return 0;
    }
    int l = 0, r = 0;
    for (int i = 0; i < N; i++) r += y[i];
    while (l < r) // first true
    {
        int m = (l + r) >> 1;
        if (check(m)) r = m;
        else l = m + 1;
    }
    int ans = get_ans(r);
    int zw = 0;
    for (int i = 0; i < N; i++)
    {
        zw += y[i];
        if (check(zw)) ans = max(ans, get_ans(zw));
    }
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...