Submission #1335960

#TimeUsernameProblemLanguageResultExecution timeMemory
1335960yhkhooBikeparking (EGOI24_bikeparking)C++17
16 / 100
43 ms10220 KiB
#include <bits/stdc++.h>
using namespace std;

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int sx = 0;
    vi x(n,0), y(n,0), xl, py(n, 0);
    for(int i=0; i<n; i++){
		cin >> y[i];
		if(i){
			py[i] = py[i-1];
		}
		py[i] += y[i];
	}
    for(int i=0; i<n; i++){
		cin >> x[i];
		sx += x[i];
        if(sx > 1000000) return 0;
		for(int j=0; j<x[i]; j++){
            xl += i;
        }
	}
	auto ty = y;
	int ans = 0, typ = 0;
    deque<int> d1, d2;
	for(int i=0; i<sx; i++){
		if(!(ty[typ])) typ++;
		if(typ < xl[i]){
			ans++;
		}
		else if(typ == xl[i]){
            d1.push_back(i);
		}
		else{
            d2.push_back(i);
			ans--;
		}
		ty[typ]--;
	}
    int answer = ans;
	for(int i=1; i<=sx; i++){
        //cerr << i << ':' << '\n';
        //cerr << ans << ' ' << d2.front() << ':' << bs(py, d2.front() - i) << ' ' << d1.front() << ':' << bs(py, d1.front() - i) << '\n';
		if(xl[i-1] > bs(py, 0)){
			ans -= 2;
		}
		else if(xl[i-1] == bs(py, 0)){
			ans -= 1;
		}
        while(d2.size() && d2.front() < i){
            d2.pop_front();
        }
        //cerr << "d2\n";
        while(d2.size() && xl[d2.front()] >= bs(py, d2.front() - i)){
            //cerr << d2.front() << ' ' << bs(py, d2.front() - i) << '\n';
            ans++;
            d1.push_back(d2.front());
            d2.pop_front();
        }
        while(d1.size() && d1.front() < i){
            d1.pop_front();
        }
        //cerr << "d1\n";
        while(d1.size() && xl[d1.front()] > bs(py, d1.front() - i)){
            //cerr << d1.front() << ' ' << bs(py, d1.front() - i) << '\n';
            ans++;
            d1.pop_front();
        }
        if(ans > answer){
            answer = ans;
        }
	}
	cout << answer;
	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...