Submission #27864

#	Time	Username	Problem	Language	Result	Execution time	Memory
27864		khsoo01	Sparklers (JOI17_sparklers)	C++11	0 / 100	0 ms	2804 KiB

sparklers

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, inf = 2e9;
ll n, k, t, a[N], gp;

vector<ll> fw, bw;

void conv (vector<ll> &A, vector<pll> &B) {
	if(A.empty()) return;
	vector<ll> tmp;
	for(ll i=0,S=0;i<A.size();i++) {
		S += A[i];
		if(i+1 == A.size() || (A[i] >= 0) != (A[i+1] >= 0)) {
			tmp.push_back(S); S = 0;
		}
	}
	if(tmp[0] >= 0) gp += tmp[0];
	for(ll i=(tmp[0] >= 0);i<tmp.size();) {
		ll P = tmp[i], C = tmp[i]; i++;
		while(i<tmp.size() && P < 0) {
			P += tmp[i]; C = min(C, P); i++;
		}
		B.push_back(pll(C, P));
	}
}

bool can (ll X) {
	vector<ll> tf, tb;
	vector<pll> cf, cb;
	for(auto &T : fw) tf.push_back(2*t*X-T);
	for(auto &T : bw) tb.push_back(2*t*X-T);
	gp = 0;
	conv(tf, cf); conv(tb, cb);
	for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
		if(i<cf.size() && gp+cf[i].X >= 0 && cf[i].Y >= 0) {
			gp += cf[i].Y; i++; continue;
		}
		if(j<cb.size() && gp+cb[j].X >= 0 && cb[j].Y >= 0) {
			gp += cb[j].Y; j++; continue;
		}
		if(i == cf.size()) {
			if(gp + cb[j].X >= 0) {j++; continue;}
			return false;
		}
		if(j == cb.size()) {
			if(gp + cf[i].X >= 0) {i++; continue;}
			return false;
		}
		if(cf[i].X < cb[j].X && gp + cf[i].X >= 0) {gp += cf[i].Y; i++; continue;}
		if(gp + cb[j].X >= 0) {gp += cb[j].Y; j++; continue;}
		return false;
	}
	return true;
}

int main()
{
	scanf("%lld%lld%lld",&n,&k,&t);
	bool f = false;
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		if(a[i] != a[i-1]) f = true;
	}
	if(!f) {puts("0"); return 0;}
	for(ll i=k-1;i>=1;i--) fw.push_back(a[i+1]-a[i]);
	for(ll i=k+1;i<=n;i++) bw.push_back(a[i]-a[i-1]);
	ll S = 1, E = (inf+t-1)/t;
	while(S < E) {
		ll M = (S+E)/2;
		can(M) ? E = M : S = M+1;
	}
	printf("%lld\n",S);
}

Compilation message (stderr)

sparklers.cpp: In function 'void conv(std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&)':
sparklers.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,S=0;i<A.size();i++) {
                  ^
sparklers.cpp:17:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 == A.size() || (A[i] >= 0) != (A[i+1] >= 0)) {
          ^
sparklers.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=(tmp[0] >= 0);i<tmp.size();) {
                          ^
sparklers.cpp:24:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(i<tmp.size() && P < 0) {
          ^
sparklers.cpp: In function 'bool can(ll)':
sparklers.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
                  ^
sparklers.cpp:38:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0,j=0;i<cf.size()||j<cb.size();) {
                               ^
sparklers.cpp:39:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<cf.size() && gp+cf[i].X >= 0 && cf[i].Y >= 0) {
       ^
sparklers.cpp:42:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j<cb.size() && gp+cb[j].X >= 0 && cb[j].Y >= 0) {
       ^
sparklers.cpp:45:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == cf.size()) {
        ^
sparklers.cpp:49:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j == cb.size()) {
        ^
sparklers.cpp: In function 'int main()':
sparklers.cpp:62:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&k,&t);
                                ^
sparklers.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

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