Submission #55380

#	Time	Username	Problem	Language	Result	Execution time	Memory
55380		ksun48	Sparklers (JOI17_sparklers)	C++14	100 / 100	231 ms	33620 KiB

sparklers

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

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 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++){
		curmin = min(curmin, a[i]);
		if(a[i] >= acur){
			acur = a[i];
			acompress.push_back({acur, curmin});
			curmin = a[i];
		}
	}
	LL bcur = b[0];
	LL curmax = b[0];
	for(LL i = 0; i < b.size(); i++){
		curmax = max(curmax, b[i]);
		if(b[i] <= bcur){
			bcur = b[i];
			bcompress.push_back({bcur, curmax});
			curmax = b[i];
		}
	}
	LL i = 0;
	LL j = 0;
	while(i + 1 < acompress.size() || j + 1 < bcompress.size()){
		if(j + 1 < bcompress.size() && bcompress[j+1].second <= acompress[i].first){
			j++;
		} else if(i + 1 < acompress.size() && bcompress[j].first <= acompress[i+1].second){
			i++;
		} else {
			return 0;
		}
	}
	return 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;
	}
	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(okay(a,b)){
			e = m;
		} else {
			s = m;
		}
	}
	cout << e << '\n';
}

Compilation message (stderr)

sparklers.cpp: In function 'LL ok(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:7:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < a.size(); i++){
                 ~~^~~~~~~~~~
sparklers.cpp:8:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < b.size(); j++){
                  ~~^~~~~~~~~~
sparklers.cpp: In function 'LL reach(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i = 0; i < a.size(); i++){
                ~~^~~~~~~~~~
sparklers.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i = 0; i < b.size(); i++){
                ~~^~~~~~~~~~
sparklers.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i + 1 < acompress.size() || j + 1 < bcompress.size()){
        ~~~~~~^~~~~~~~~~~~~~~~~~
sparklers.cpp:45:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i + 1 < acompress.size() || j + 1 < bcompress.size()){
                                    ~~~~~~^~~~~~~~~~~~~~~~~~
sparklers.cpp:46:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j + 1 < bcompress.size() && bcompress[j+1].second <= acompress[i].first){
      ~~~~~~^~~~~~~~~~~~~~~~~~
sparklers.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   } else if(i + 1 < acompress.size() && bcompress[j].first <= acompress[i+1].second){
             ~~~~~~^~~~~~~~~~~~~~~~~~
sparklers.cpp: In function 'LL okay(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL j = 0; j < a.size(); j++){
                ~~^~~~~~~~~~
sparklers.cpp:63: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: 50 / 50