제출 #1336716

#제출 시각아이디문제언어결과실행 시간메모리
1336716edl0231Bikeparking (EGOI24_bikeparking)C++20
16 / 100
70 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;
}
void 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]);
    }
    cout << ans - c << '\n';
    return;
}
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;
    }
    get_ans(r);
}
#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...