Submission #1225426

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

sparklers

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

int N,K;
long long int T;
int lst[1100];

int main(){
	
	scanf(" %d",&N);
	scanf(" %d",&K);
	scanf(" %lld",&T);
	
	for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
	
	int s = 0;
	int e = (N-1+1e9)/N;

	while(s != e){
		int m = (s + e)/2;
		
		m *= 2;
		
		long long int cesh = T * m;
		
		int it = K - 1;
		int it1 = K + 1;
		
		pair<long long int, long long int> profeet = {0,0};
		pair<long long int, long long int> profeet1 = {0,0};
		
		bool one = false;
		
		while(it != 0 && (!one || profeet.first < 0) ){
			one = true;
			profeet.first += T * m - (lst[it + 1] - lst[it]);
			profeet.second = min(profeet.second,profeet.first - T * m);
			it--;
		}
		
		one = false;
		
		while(it1 != N + 1 && (!one || profeet1.first < 0) ){
			one = true;
			profeet1.first += T * m - (lst[it1] - lst[it1 - 1]);
			profeet1.second = min(profeet1.second,profeet1.first - T * m);
			it1++;
		}
		
		int l = K;
		int r = K;
		
		while(l != 1 && r != N){
			if(cesh >= -min(profeet.second, profeet1.second)){
				if(profeet.first > profeet1.first){
					cesh += profeet.first;
					l = it + 1;
					
					one = false;
					profeet = {0,0};
					
					while(it != 0 && (!one || profeet.first < 0) ){
						one = true;
						profeet.first += T * m - (lst[it + 1] - lst[it]);
						profeet.second = min(profeet.second,profeet.first - T * m);
						it--;
					}
				}
				else{
					cesh += profeet1.first;
					r = it1 - 1;
					
					one = false;
					profeet1 = {0,0};
					
					while(it1 != N + 1 && (!one || profeet1.first < 0) ){
						one = true;
						profeet1.first += T * m - (lst[it1] - lst[it1 - 1]);
						profeet1.second = min(profeet1.second,profeet1.first - T * m);
						it1++;
					}
				}
			}
			else if(cesh < -max(profeet.second, profeet1.second)){
				break;
			}
			else{
				if(cesh >= -profeet.second){
					cesh += profeet.first;
					l = it + 1;
					
					one = false;
					profeet = {0,0};
					
					while(it != 0 && (!one || profeet.first < 0) ){
						one = true;
						profeet.first += T * m - (lst[it + 1] - lst[it]);
						profeet.second = min(profeet.second,profeet.first - T * m);
						it--;
					}
				}
				else{
					cesh += profeet1.first;
					r = it1 - 1;
					
					one = false;
					profeet1 = {0,0};
					
					while(it1 != N + 1 && (!one || profeet1.first < 0) ){
						one = true;
						profeet1.first += T * m - (lst[it1] - lst[it1 - 1]);
						profeet1.second = min(profeet1.second,profeet1.first - T * m);
						it1++;
					}
				}
			}
		}
		//printf("%d %d %d\n",l,r,cesh);
		if(l == 1){
			while(r != N){
				if(cesh >= lst[r + 1] - lst[r]){
					cesh += T * m - (lst[r + 1] - lst[r]);
				}
				else break;
				r++;
			}
		}
		if(r == N){
			while(l != 1){
				if(cesh >= lst[l] - lst[l - 1]){
					cesh += T * m - (lst[l] - lst[l - 1]);
				}
				else break;
				l--;
			}
		}
		
		
		m/= 2;
		
		//printf("%d %d %d %lld\n",l,r,m,cesh);
		
		if(l == 1 && r == N){
			e = m;
		}
		else s = m + 1;
	}
	
	printf("%d\n",s);
	
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
sparklers.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf(" %lld",&T);
      |         ~~~~~^~~~~~~~~~~~
sparklers.cpp:14:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         for(int i = 1; i <= N; i++) scanf(" %d",&lst[i]);
      |                                     ~~~~~^~~~~~~~~~~~~~~

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