제출 #1228201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228201		salmon	Sparklers (JOI17_sparklers)	C++20	0 / 100	0 ms	320 KiB

sparklers

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

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

int m;

bool zero;
pair<long long int, long long int> ii;
pair<long long int, long long int> ii1;

int it;
int it1;
	
void propit(){
	if(it == N + 1){
		ii = {-1,-1};
		return;
	}
	
	zero = false;
	ii = {0,0};
	while(it != N + 1 && (!zero || ii.first < 0)){
		zero = true;
		ii.first += - (lst[it] - lst[it - 1]) + T * m;
		ii.second = min(ii.first,ii.second);
		it++;
	}
}

void propit1(){
	if(it1 == 0){
		ii1 = {-1,-1};
		return;
	}
	
	zero = false;
	ii1 = {0,0};
	while(it1 != 0 && (!zero || ii1.first < 0)){
		zero = true;
		ii1.first += - (lst[it1 + 1] - lst[it1]) + T * m;
		ii1.second = min(ii1.first,ii1.second);
		it1--;
	}
}

void properit(){
	if(it == K + 1){
		ii = {-1,-1};
		return;
	}
	
	zero = false;
	ii = {0,0};
	while(it != K + 1 && (!zero || ii.first < 0)){
		zero = true;
		ii.first += (lst[it] - lst[it - 1]) - T * m;
		ii.second = min(ii.first,ii.second);
		it++;
	}
}

void properit1(){
	if(it1 == K - 1){
		ii1 = {-1,-1};
		return;
	}
	
	zero = false;
	ii1 = {0,0};
	while(it1 != K - 1 && (!zero || ii1.first < 0)){
		zero = true;
		ii1.first += (lst[it1 + 1] - lst[it1]) - T * m;
		ii1.second = min(ii1.first,ii1.second);
		it1--;
	}
}

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;
		
		::m = m;
		
		__int128 cesh = T * m;
		
		bool zero = false;
		
		int l = K; 
		int r = K;
		
		it = K + 1;
		it1 = K - 1;
		
		propit();
		propit1();
		
		while(l != 1 || r != N){
			if(max(ii.first,ii1.first) < 0) break;
			if(cesh + max(ii.second,ii1.second) - T * m < 0) break;
			if(cesh + min(ii.second,ii1.second) - T * m > 0){
				if(max(ii.first,ii1.first) == ii.first){
					cesh += ii.first;
					r = it - 1;
					propit();
				}
				else{
					cesh += ii.second;
					l = it1 + 1;
					propit1();
				}
			}
			else{
				if(max(ii.second,ii1.second) == ii.second){
					if(ii.first < 0) break;
					
					cesh += ii.first;
					r = it - 1;
					propit();
				}
				else{
					if(ii1.first < 0) break;
					
					cesh += ii1.first;
					l = it1 + 1;
					propit1();
				}
			}
		}
		
		cesh = T * m;
		cesh *= (N - 1);
		cesh += - lst[N];
		
		int fl = 1;
		int fr = N;
		
		it = 2;
		it1 = N - 1;
		
		properit();
		properit1();
		
		while(fl != K || fr != K){
			if(max(ii.first,ii1.first) < 0) break;
			if(cesh + max(ii.second,ii1.second) - T * m < 0) break;
			if(cesh + min(ii.second,ii1.second) - T * m > 0){
				if(max(ii.first,ii1.first) == ii.first){
					cesh += ii.first;
					r = it - 1;
					properit();
				}
				else{
					cesh += ii.second;
					l = it1 + 1;
					properit1();
				}
			}
			else{
				if(max(ii.second,ii1.second) == ii.second){
					if(ii.first < 0) break;
					
					cesh += ii.first;
					r = it - 1;
					properit();
				}
				else{
					if(ii1.first < 0) break;
					
					cesh += ii1.first;
					l = it1 + 1;
					properit1();
				}
			}
		}
		
		//printf("%d %d %d %d %d\n\n",l,r,fl,fr,m/2);
		
		m/= 2;
		
		if(fl == l && fr == r){
			e = m;
		}
		else s = m + 1;
	}
	
	printf("%d\n",s);
	
}

컴파일 시 표준 에러 (stderr) 메시지

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

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