제출 #132809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132809		sebinkim	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	376 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

vector <ll> L, R;
ll X[101010];
ll n, k, t;

bool check(ll v)
{
	ll i, s, x;
	
	L.clear(); R.clear();
	
	for(i=1; i<k; i++){
		x = 2 * t * v - X[i + 1] + X[i];
		for(; !L.empty() && L.back() >= 0 && x < 0; L.pop_back()){
			x += L.back();
		}
		L.push_back(x);
	}
	
	for(i=n; i>k; i--){
		x = 2 * t * v - X[i] + X[i - 1];
		for(; !R.empty() && R.back() >= 0 && x < 0; R.pop_back()){
			x += R.back();
		}
		R.push_back(x);
	}
	
	for(s=0; !L.empty() || !R.empty(); ){
		if(!L.empty() && (R.empty() || L.back() > R.back())){
			s += L.back(); L.pop_back();
		}
		else{
			s += R.back(), R.pop_back();
		}
		if(s < 0) return 0;
	}
	
	return 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll i, s, e;
	
	cin >> n >> k >> t;
	
	for(i=1; i<=n; i++){
		cin >> X[i];
	}
	
	for(s=0, e=1e12/t; s<=e; ){
		if(check(s + e >> 1)) e = (s + e >> 1) - 1;
		else s = (s + e >> 1) + 1;
	}
	
	cout << e + 1 << "\n";
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sparklers.cpp: In function 'int main()':
sparklers.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s + e >> 1)) e = (s + e >> 1) - 1;
            ~~^~~
sparklers.cpp:61:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   if(check(s + e >> 1)) e = (s + e >> 1) - 1;
                              ~~^~~
sparklers.cpp:62:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   else s = (s + e >> 1) + 1;
             ~~^~~

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