Submission #1225496

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

sparklers

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

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

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 = 1e9;

	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 && cesh < 2 * lst[N]){
			/*printf("%d %d %lld\n",l,r,cesh);
			printf("%d %d\n",it,it1);
			printf("%lld %lld\n",profeet.first,profeet.second);
			printf("%d %d\n",profeet1.first,profeet1.second);*/
			//printf("\n");
			if(cesh >= -min(profeet.second, profeet1.second)){
				if(max(profeet.first, profeet1.first) < 0){
					long long int num = 0;
					
					if(profeet.second < profeet1.second){
						while(num != profeet.second){
							if(num == 0) num = lst[l - 1] - lst[l];
							else num += T * m + lst[l - 1] - lst[l];
							l--;
						}
						
						cesh += num + T * m;
						
						it = l - 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{
						while(num != profeet1.second){
							if(num == 0) num = lst[r] - lst[r + 1];
							else num += T * m + lst[r] - lst[r + 1];
							r++;
						}
						
						cesh += num + T * m;
						
						it1 = r + 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++;
						}
					}
					continue;
				}
				
				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++;
					}
				}
			}
		}

		if(cesh < 2 * lst[N]){
			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\n",l,r,m,cesh);
		
		if( cesh >= 2 * lst[N] || (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: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50