Submission #995764

#	Time	Username	Problem	Language	Result	Execution time	Memory
995764		jcelin	Sparklers (JOI17_sparklers)	C++14	0 / 100	1 ms	344 KiB

sparklers

#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()

typedef vector<int> vi; 
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef long double ld;

const int MAXN = 47;
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ll INF = 1e18 + 7;

ll x[MAXN], n, k, t;
vll lef, rig;
vpll L, R;

bool okej(ll poc, vpll &vec){
	for(auto &y : vec){
		if(poc + y.Y < 0) return 0;
		poc += y.X;
	}
	return poc >= 0;
}


ll balance = 0;

struct Stack {
	vector<ll> v;
	vector<ll> pre;

	int cur_idx = 0;
	int max_idx = 0;

	ll sum = 0;

	set<pair<ll, ll> > s;

	void create(vector<ll> _v) {
		cur_idx = 0;
		max_idx = 0;
		v = _v;
		sum = 0;
		pre.resize(v.size());
		pre[0] = v[0];
		for (int i = 1; i < (int)v.size(); ++i) pre[i] = v[i] + pre[i - 1];
		
		s.insert({-1e17, -1});
	}

	void extend() {
		while (max_idx < (int)v.size() && balance + pre[max_idx] - sum >= 0) {
			s.insert({pre[max_idx], max_idx});
			++max_idx;
		}
	}

	void makni() {
		int idx = (*s.rbegin()).second;

		while (cur_idx <= idx) {
			assert(s.find({pre[cur_idx], cur_idx}) != s.end());
			s.erase(s.find({pre[cur_idx], cur_idx}));

			balance += v[cur_idx];
			sum += v[cur_idx];
			++cur_idx;
		}
	}

	ll delta() {
		return (*s.rbegin()).first - sum;
	}

} A, B;

bool resi(vector<ll> a, vector<ll> b) {
	A.create(a);
	B.create(b);

	A.extend();
	B.extend();

	while (balance + max(A.delta(), B.delta()) >= 0) {

		if (A.delta() > B.delta()) A.makni();
		else B.makni();

		A.extend();
		B.extend();
	}

	return (A.cur_idx == (int)a.size() && B.cur_idx == (int)b.size());
}

bool check(ll mid){
	lef.clear();
	rig.clear();
	L.clear();
	R.clear();
	for(int i=k; i<n; i++) rig.PB((ll)2 * mid * t - (ll)(x[i + 1] - (ll)x[i]) / 2);
	for(int i=1; i<k; i++) lef.PB((ll)2 * mid * t - (ll)(x[i + 1] - (ll)x[i]) / 2);
	
	reverse(all(rig));
	balance = 0;
	return resi(lef, rig);
}

void solve(){
	cin >> n >> k >> t;
	for(int i=1; i<=n; i++) cin >> x[i], x[i] *= 2;
	
	int lo = 1, hi = ((1e9 + 1) / t) + 1, ret = -1;
	while(lo <= hi){
		int mid = (lo + hi) / 2;
		if(check(mid)) hi = mid - 1, ret = mid;
		else lo = mid + 1;
	}
	cout << ret << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> t;
	while(tt--) solve();
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50