Submission #140444

#	Time	Username	Problem	Language	Result	Execution time	Memory
140444		dndhk	Sparklers (JOI17_sparklers)	C++14	100 / 100	41 ms	3052 KiB

sparklers

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL

const int MAX_N = 100000;

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, K;
ll T;
vector<ll> v;

ll D[MAX_N+1];

bool chk(ll x){
	for(int i=0; i<N; i++)	D[i] = (ll)2 * T * (ll)i * x - v[i];
	int pl=K, pr=K, nl=K-1, nr=K+1;
	while(1){
		while(D[nl]>D[pl] && D[nl]<=D[pr] && nl>0)	nl--;
		while(D[nr]<D[pr] && D[nr]>=D[pl] && nr<N-1)	nr++;
		bool ch = false;
		if(nl>=0 && D[nl]<=D[pl]){
			pl = nl; nl--;
			ch = true;
		}
		if(nr<N && D[nr]>=D[pr]){
			pr = nr; nr++;
			ch = true;
		}
		if(!ch)	break;
	}
	if((nr<N && D[pl]>D[nr]) || (nl>=0 && D[pr]<D[nl]))	return false;
	int l = 0, r = N-1; nl = 1; nr = N-2;
	while(1){
		while(D[l]<D[nl] && D[nl]<=D[r] && nl<K)	nl++;
		while(D[l]<=D[nr] && D[nr]<D[r] && K<nr)	nr--;
		bool ch = false;
		if(nl<=K && D[nl]<=D[l]){
			l = nl; nl++;
			ch = true;
		}
		if(nr>=K && D[nr]>=D[r]){
			r = nr; nr--;
			ch = true;
		}
		if(!ch)	break;
	}
	return ((pl<=l) && (r<=pr));
}

int main(){
	scanf("%d%d%lld", &N, &K, &T);
	K--;
	for(int i=0; i<N; i++){
		ll x; scanf("%lld", &x);
		v.pb(x);
	}
	ll s = 0, e = INF, m;
	while(s<e){
		m = (s+e)/2;
		if(chk(m)){
			e = m;
		}else{
			s = m+1;
		}
	}
	printf("%lld", s);
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &K, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
         ~~~~~^~~~~~~~~~~~

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