Submission #1336746

#TimeUsernameProblemLanguageResultExecution timeMemory
1336746edl0231Bikeparking (EGOI24_bikeparking)C++20
0 / 100
66 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)
{
    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 - c;
}
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 << 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++)
    {
        if (y[i] != 0) {zw = i; break;}
    }
    if (check(y[zw])) ans = max(ans, get_ans(y[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...