Submission #55347

#	Time	Username	Problem	Language	Result	Execution time	Memory
55347		ksun48	Sparklers (JOI17_sparklers)	C++14	50 / 100	22 ms	4856 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL reach(vector<LL> a, vector<LL> b){
	if(a[0] < b[0]) return 0;
	vector<pair<LL,LL> > acompress, bcompress;
	LL acur = a[0];
	LL curmin = a[0];
	for(LL i = 0; i < a.size(); i++){
		if(a[i] >= acur){
			acompress.push_back({acur, curmin});
			acur = a[i];
			curmin = a[i];
		}
		curmin = min(curmin, a[i]);
	}
	assert(acur == a[a.size()-1]);
	LL bcur = b[0];
	LL curmax = b[0];
	for(LL i = 0; i < b.size(); i++){
		if(b[i] <= bcur){
			bcompress.push_back({bcur, curmax});
			bcur = b[i];
			curmax = b[i];
		}
		curmax = max(curmax, b[i]);
	}
	assert(bcur == b[b.size()-1]);
	LL i = 0;
	LL j = 0;
	while(i < acompress.size() - 1 && j < bcompress.size() - 1){
		if(bcompress[j+1].second <= acompress[i].first){
			j++;
		} else if(bcompress[j].first <= acompress[i+1].second){
			i++;
		} else {
			return 0;
		}
	}
	return 1;
}

LL ok(vector<LL> a, vector<LL> b){
	LL dp[a.size()][b.size()];
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < b.size(); j++){
			dp[i][j] = 0;
			if(a[i] >= b[j]){
				if((i == 0 && j == 0) || (i > 0 && dp[i-1][j]) || (j > 0 && dp[i][j-1])){
					dp[i][j] = 1;
				}
			}
		}
	}
	return dp[a.size()-1][b.size()-1];
}

LL okay(vector<LL> a, vector<LL> b){
	LL ma = 0;
	LL mb = 0;
	for(LL j = 0; j < a.size(); j++){
		if(a[j] > a[ma]) ma = j;
	}
	for(LL j = 0; j < b.size(); j++){
		if(b[j] < b[mb]) mb = j;
	}
	if(a[ma] < b[mb]) return 0;
	vector<LL> la, lb;
	vector<LL> ra, rb;
	for(LL j = 0; j <= ma; j++) la.push_back(a[j]);
	for(LL j = a.size()-1; j >= ma; j--) ra.push_back(a[j]);
	for(LL j = 0; j <= mb; j++) lb.push_back(b[j]);
	for(LL j = b.size()-1; j >= mb; j--) rb.push_back(b[j]);
	return reach(la, lb) && reach(ra, rb);
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	LL n, k, t;
	cin >> n >> k >> t;
	k--;
	vector<LL> x(n);
	for(LL i = 0; i < n; i++){
		cin >> x[i];
	}		
	LL s = -1;
	LL e = 1000000000;
	while(s + 1 < e){
		LL m = (s + e) / 2;
		vector<LL> y = x;
		for(LL i = 0; i < n; i++){
			y[i] -= m * t * 2 * i;
		}
		vector<LL> a, b;
		for(LL i = k; i >= 0; i--){
			a.push_back(y[i]);
		}
		for(LL i = k; i < n; i++){
			b.push_back(y[i]);
		}
		if(ok(a,b)){
			e = m;
		} else {
			s = m;
		}
	}
	cout << e << '\n';
}

Compilation message (stderr)

sparklers.cpp: In function 'LL reach(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:10:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i = 0; i < a.size(); i++){
                ~~^~~~~~~~~~
sparklers.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i = 0; i < b.size(); i++){
                ~~^~~~~~~~~~
sparklers.cpp:32:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < acompress.size() - 1 && j < bcompress.size() - 1){
        ~~^~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:32:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i < acompress.size() - 1 && j < bcompress.size() - 1){
                                    ~~^~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp: In function 'LL ok(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
sparklers.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < b.size(); j++){
                  ~~^~~~~~~~~~
sparklers.cpp: In function 'LL okay(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL j = 0; j < a.size(); j++){
                ~~^~~~~~~~~~
sparklers.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL j = 0; j < b.size(); j++){
                ~~^~~~~~~~~~

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