제출 #1336744

#제출 시각아이디문제언어결과실행 시간메모리
1336744edl0231Bikeparking (EGOI24_bikeparking)C++20
25 / 100
115 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);
    for (int i = 0; i < N; i++) cin >> x[i];
    for (int i = 0; i < N; i++) cin >> y[i];
    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...