Submission #1226286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226286		_rain_	Sparklers (JOI17_sparklers)	C++20	0 / 100	0 ms	328 KiB

sparklers

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

const int N=(int)1e6;
const long double eps=1e-17;
	int x[N+2];
	int n,k;
LL X[N+2];
LL t;

bool possible(LL s){
	for(int i=1;i<k;++i) X[i]=t*s*2-(x[i+1]-x[i]);
	for(int i=k+1;i<=n;++i) X[i]=t*s*2-(x[i]-x[i-1]);
	int l=k,r=k;
	LL sum=0;
	while (true){
		if (l-1>=1 && (sum+X[l-1])>=0){
			--l;
			sum+=X[l];
		}
		else if (r+1<=n && (sum+X[r+1])>=0){
			++r;
			sum+=X[r];
		}
		else break;
	}
	return l==1 && r==n;
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
	
	cin>>n>>k>>t;
	for(int i=1;i<=n;++i) cin>>x[i];
	
	int low=0,high=(int)1e9,ans=-1;
	while (low<=high){
		int mid=(low+high)/2;
		if (possible(mid)){
			ans=mid;
			high=mid-1;
		}
		else low=mid+1;
	}

	cout<<ans;
	
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:37:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:38:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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