제출 #1335873

#제출 시각아이디문제언어결과실행 시간메모리
1335873justin271828Bikeparking (EGOI24_bikeparking)C++20
25 / 100
142 ms2868 KiB
#include <bits/stdc++.h>
using namespace std;

int N;
int x[314159];
int y[314159];

int f(int n) {
    int ans = 0;
    int xpos = 0;
    int xtemp = x[0];
    int ypos = n;
    int ytemp = y[n];
    while (true) {
        if (ypos >= N) {
            ypos -= N;
            ytemp = y[ypos];}
        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;
}

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