제출 #1336000

#제출 시각아이디문제언어결과실행 시간메모리
1336000yhkhooBikeparking (EGOI24_bikeparking)C++17
16 / 100
1092 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

using vi = basic_string<int>;
#define all(v) (v).begin(), (v).end()
#define bs(v, x) upper_bound(all(v), x) - (v).begin()

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vi x(n, 0), y(n, 0), yl, xp(n, 0);
    for(int i=0; i<n; i++){
        cin >> x[i];
        if(i){
            xp[i] = xp[i-1];
        }
        xp[i] += x[i];
    }
    for(int i=0; i<n; i++){
        cin >> y[i];
        for(int j=0; j<y[i]; j++){
            yl += i;
        }
    }
    deque<int> v1, v2;
    int cur = 0;
    for(int i=0; i<yl.size(); i++){
        int t = bs(xp, i);
        int& s = yl[i];
        if(t < s){
            cur++;
        }
        else if(t == s){
            v1.push_back(i);
        }
        else{
            v2.push_back(i);
            cur--;
        }
    }
    int ans = cur;
    int ft = bs(xp, 0);
    for(int i=1; i<yl.size(); i++){
        if(ft < yl[i-1]){
            cur -= 2;
        }
        else if(ft == yl[i-1]){
            cur -= 1;
        }
        else{
            break;
        }
        while(v2.size() && v2.front() < i){
            v2.pop_front();
        }
        while(v2.size() && bs(xp, v2.front() - i) <= yl[v2.front()]){
            cur++;
            v1.push_back(v2.front());
            v2.pop_front();
        }
        while(v1.size() && v1.front() < i){
            v1.pop_front();
        }
        while(v1.size() && bs(xp, v1.front() - i) < yl[v1.front()]){
            cur++;
            v1.pop_front();
        }
        if(cur > ans){
            ans = cur;
        }
    }
    cout << ans;
    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...