Submission #57759

#	Time	Username	Problem	Language	Result	Execution time	Memory
57759		spencercompton	Sparklers (JOI17_sparklers)	C++17	0 / 100	2 ms	652 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll t;
bool v[1001][1001];
ll pos[1001];
// ll dp[2][1000][1000];
// ll pos[1000];
vector<ll> all;
// bool go(int l, int r){
// 	if((pos[r]-pos[l]>2LL*t*(ll)(r-l))){
// 		return false;
// 	}
// 	if(v[l][r]){
// 		return false;
// 	}
// 	if(l==0 && r==n-1){
// 		return true;
// 	}
// 	v[l][r] = true;
// 	if(l>0 && go(l-1,r)){
// 		return true;
// 	}
// 	if(r<n-1 && go(l,r+1)){
// 		return true;
// 	}
// 	return false;

// }
int main(){
	ll tt;
	cin >> n >> k >> tt;
	for(int i = 0; i<n; i++){
		cin >> pos[i];
	}
	k--;
	ll low = 0LL;
	ll high = 1000000000LL;
	while(low<high){
		ll mid = (low+high)/2LL;
		t = mid*tt;
		vector<ll> ar[2];
		for(int i = 0; i<2; i++){
			ar[i].push_back(0);
		}
		for(int i = k+1; i<n; i++){
			ar[0].push_back(ar[0][ar[0].size()-1] + 2LL * t - (pos[i]-pos[i-1]));
		}
		for(int i = k-1; i>=0; i--){
			ar[1].push_back(ar[1][ar[1].size()-1] + 2LL * t - (pos[i+1] - pos[i]));
		}
		// if(mid==9LL){
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<ar[i].size(); j++){
		// 			cout << ar[i][j] << " ";
		// 		}
		// 		cout << endl;
		// 	}
		// }
		vector<pair<int, ll> > f[2];
		vector<pair<int, ll> > b[2];
		vector<ll> pre[2];
		for(int i = 0; i<2; i++){
			f[i].push_back(make_pair(0,0));
			int sz = 1;
			for(int j = 1; j<ar[i].size(); j++){
				if(ar[i][j] > ar[i][f[i][sz-1].first]){
					sz++;
					f[i].push_back(make_pair(j,ar[i][j]));
				}
			}
			for(int j = 0; j+1<sz; j++){
				for(int a = f[i][j].first; a<f[i][j+1].first; a++){
					f[i][j].second = min(f[i][j].second,ar[i][a]);
				}
			}
			sz = 1;
			b[i].push_back(make_pair(ar[i].size()-1,ar[i][ar[i].size()-1]));
			for(int j = ar[i].size()-2; j>=0; j--){
				if(ar[i][j] > ar[i][b[i][sz-1].first]){
					sz++;
					b[i].push_back(make_pair(j,ar[i][j]));
				}
			}
			for(int j = 0; j+1<sz; j++){
				for(int a = b[i][j+1].first+1; a<=b[i][j].first; a++){
					b[i][j].second = min(b[i][j].second,ar[i][a]);
				}
			}
			pre[i].resize(sz);
			pre[i][sz-1] = b[i][sz-1].second;
			for(int j = sz-2; j>=0; j--){
				pre[i][j] = min(b[i][j].second,pre[i][j+1]);
			}
		}
		bool ok = true;
		int p1 = 0;
		int p2 = 0;
		while(p1+1<f[0].size() || p2+1<f[1].size()){
			if(p1+1<f[0].size() && ar[1][f[1][p2].first] + f[0][p1].second >=0LL){
				p1++;
			}
			else if(p2+1<f[1].size() && ar[0][f[0][p1].first] + f[1][p2].second >= 0LL){
				p2++;
			}
			else{
				ok = false;
				break;
			}
		}
		if(!ok){
			low = mid+1LL;
			continue;
		}
		p1 = 0;
		p2 = 0;
		// if(mid==9){
		// 	cout << "TEMP " << endl;
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<pre[i].size(); j++){
		// 			cout << pre[i][j] << " ";
		// 		}
		// 		cout << endl;
		// 	}
		// 	for(int i = 0; i<2; i++){
		// 		for(int j = 0; j<pre[i].size(); j++){
		// 			cout << b[i][j].first << "," << b[i][j].second << " ";
		// 		}
		// 		cout << endl;
		// 	}
		// }
		while(p1+1<b[0].size() || p2+1<b[1].size()){
			if(p1+1<b[0].size() && ar[1][b[1][p2].first] + b[0][p1].second >= 0LL && ar[0][b[0][p1+1].first] + pre[1][p2] >=0LL){
				p1++;
			}
			else if(p2+1<b[1].size() && ar[0][b[0][p1].first] + b[1][p2].second >= 0LL && ar[1][b[1][p2+1].first] + pre[0][p1] >=0LL){
				p2++;
			}
			else {
				ok = false;
				break;
			}
		}
		// cout << mid << " " << ok << endl;
		if(!ok){
			low = mid+1LL;
		}
		else{
			high = mid;
		}
	}
	cout << low << endl;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 1; j<ar[i].size(); j++){
                   ~^~~~~~~~~~~~~
sparklers.cpp:100:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<f[0].size() || p2+1<f[1].size()){
         ~~~~^~~~~~~~~~~~
sparklers.cpp:100:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<f[0].size() || p2+1<f[1].size()){
                             ~~~~^~~~~~~~~~~~
sparklers.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(p1+1<f[0].size() && ar[1][f[1][p2].first] + f[0][p1].second >=0LL){
       ~~~~^~~~~~~~~~~~
sparklers.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(p2+1<f[1].size() && ar[0][f[0][p1].first] + f[1][p2].second >= 0LL){
            ~~~~^~~~~~~~~~~~
sparklers.cpp:133:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<b[0].size() || p2+1<b[1].size()){
         ~~~~^~~~~~~~~~~~
sparklers.cpp:133:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<b[0].size() || p2+1<b[1].size()){
                             ~~~~^~~~~~~~~~~~
sparklers.cpp:134:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(p1+1<b[0].size() && ar[1][b[1][p2].first] + b[0][p1].second >= 0LL && ar[0][b[0][p1+1].first] + pre[1][p2] >=0LL){
       ~~~~^~~~~~~~~~~~
sparklers.cpp:137:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(p2+1<b[1].size() && ar[0][b[0][p1].first] + b[1][p2].second >= 0LL && ar[1][b[1][p2+1].first] + pre[0][p1] >=0LL){
            ~~~~^~~~~~~~~~~~

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