Submission #1335941

#TimeUsernameProblemLanguageResultExecution timeMemory
1335941justin271828Bikeparking (EGOI24_bikeparking)C++20
44 / 100
200 ms7680 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int N;
int x[314159];
int pref[314159];
int y[314159];
int sumy = 0;

int f(int n) {
    if (n >= sumy) return -1234567890;
    int ans = 0;
    int xpos = 0;
    int xtemp = x[0];
    int lo = 0;
    int hi = N;
    int mid;
    while (true) {
        mid = (lo+hi)/2;
        if (pref[mid] > n) hi = mid-1;
        else if (pref[mid+1] <= n) lo = mid+1;
        else break;
    }
    int ypos = mid;
    int ytemp = y[ypos]-(n-pref[mid]);
    int yposi = ypos;
    int minus = ytemp;
    bool b = false;
    while (true) {
        if (ypos >= N) {
            b = true;
            ypos -= N;
            ytemp = y[ypos];}
        if (ypos == yposi && b) ytemp -= minus;
        if (xpos == N) break;
        if (xtemp > ytemp) {
            xtemp -= ytemp;
            if (xpos > ypos) ans -= ytemp;
            else if (xpos < ypos) ans += ytemp;
            ytemp = y[++ypos];
        }
        else if (xtemp == ytemp) {
            if (xpos > ypos) ans -= ytemp;
            else if (xpos < ypos) ans += ytemp;
            xtemp = x[++xpos];
            ytemp = y[++ypos];
        }
        else {
            ytemp -= xtemp;
            if (xpos > ypos) ans -= xtemp;
            else if (xpos < ypos) ans += xtemp;
            xtemp = x[++xpos];
        }
    }
    return ans;
}

int32_t main() {
    cin >> N;
    memset(x, 0, sizeof(x));
    memset(y, 0, sizeof(y));
    for (int i = 0; i < N; i++) cin >> x[i];
    for (int i = 0; i < N; i++) {
        cin >> y[i];
        sumy += y[i];
    }
    if (N == 1) {
        cout << 0;
        return 0;
    }
    int sumx = 0;
    for (int i = 0; i < N; i++) {
        if (sumx == sumy) {
            x[i] = 0;
            continue;}
        if (sumx + x[i] > sumy) {
            x[i] = sumy-sumx;
            sumx = sumy;
            continue;
        }
        sumx += x[i];
    }
    pref[0] = 0;
    for (int i = 0; i < N; i++) pref[i+1] = pref[i]+y[i];
    //f(9);
    //return 0;
    if (sumx >= 2 && f(0) > f(1)) {
        cout << f(0);
        return 0;
    }
    if (sumx == 0) {
        cout << 0;
        return 0;
    }
    int lo = 0;
    int hi = sumx-1;
    int mid;
    while (true) {
        mid = (lo+hi)/2;
        if (mid > 0 && f(mid) < f(mid-1)) hi = mid-1;
        else if (mid < sumx-2 && f(mid) < f(mid+1)) lo = mid+1;
        else break;
    }
    cout << f(mid);
    return 0;
}
#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...