oj.uz

답안 #59848

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59848 2018-07-23T08:03:45 Z 정원준(#1727) Sparklers (JOI17_sparklers) C++11
0 / 100
 4 ms 560 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L N,K,T;
L loc[100010];
L a[100010];

L vlfdy[100010];
L gain[100010];


bool ok(L x){
	L t=x*T*2;
	//printf("***%lld %lld***\n",x,t);
	L i,s=K,e=K,health=t;
	/*while(s>1&&e<N)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t1=loc[s]-loc[s-1];
		L t2=loc[e+1]-loc[e];
		if(t1<t2)
		{
			if(t1>left) return 0;
			left=left-t1+t;
			s--;
		}
		else
		{
			if(t2>left) return 0;
			left=left-t2+t;
			e++;
		}
	}
	while(s>1)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t1=loc[s]-loc[s-1];
		if(t1>left) return 0;
		left=left-t1+t;
		s--;
	}
	while(e<N)
	{
		printf("%lld %lld %lld\n",s,e,left);
		L t2=loc[e+1]-loc[e];
		if(t2>left) return 0;
		left=left-t2+t;
		e++;
	}*/
	queue<L>lloc,lvlfdy,lgain;
	queue<L>rloc,rvlfdy,rgain;
	
	health=0;
	for(i=K-1;i>=1;i--)
	{
		health+=loc[i+1]-loc[i];
		vlfdy[i]=max(vlfdy[i+1],health);
		health-=t;
		gain[i]=-health;
		if(gain[i]>0)
		{
			lloc.push(i);
			lvlfdy.push(vlfdy[i]);
			lgain.push(gain[i]);
			health=0;
			vlfdy[i]=0;
		}
	}
	health=0;
	for(i=K+1;i<=N;i++)
	{
		health+=loc[i]-loc[i-1];
		vlfdy[i]=max(vlfdy[i-1],health);
		health-=t;
		gain[i]=-health;		
		if(gain[i]>0)
		{
			rloc.push(i);
			rvlfdy.push(vlfdy[i]);
			rgain.push(gain[i]);
			health=0;
			vlfdy[i]=0;
		}
	}
	/*for(i=1;i<=N;i++)
	{
		printf("%lld %lld\n",vlfdy[i],gain[i]);
	}*/
	health=t;
	while(!lloc.empty()&&!rloc.empty())
	{
		if(lvlfdy.front()<=health)
		{
			health+=lgain.front();
			s=lloc.front();
			lloc.pop();
			lvlfdy.pop();
			lgain.pop();
		}
		else if(rvlfdy.front()<=health)
		{
			health+=rgain.front();
			e=rloc.front();
			rloc.pop();
			rvlfdy.pop();
			rgain.pop();
		}
		else return 0;
	}
	while(!lloc.empty())
	{
		if(lvlfdy.front()<=health)
		{
			health+=lgain.front();
			s=lloc.front();
			lloc.pop();
			lvlfdy.pop();
			lgain.pop();
		}
		else return 0;
	}
	while(!rloc.empty())
	{
		if(rvlfdy.front()<=health)
		{
			health+=rgain.front();
			e=rloc.front();
			rloc.pop();
			rvlfdy.pop();
			rgain.pop();
		}
		else return 0;
	}
	//printf("%lld %lld\n",s,e);
	while(s>1)
	{
		//printf("%lld %lld %lld\n",s,e,left);
		L t1=loc[s]-loc[s-1];
		if(t1>health) return 0;
		health=health-t1+t;
		s--;
	}
	while(e<N)
	{
		//printf("%lld %lld %lld\n",s,e,left);
		L t2=loc[e+1]-loc[e];
		if(t2>health) return 0;
		health=health-t2+t;
		e++;
	}
	return 1;
}

L bin(L s,L e){
	if(s==e) return s;
	L mid=(s+e)/2;
	if(ok(mid)) return bin(s,mid);
	else return bin(mid+1,e);
}

int main()
{
	scanf("%lld %lld %lld",&N,&K,&T);
	L i,st;
	for(i=1;i<=N;i++)
	{
		scanf("%lld",&loc[i]);
	}
	st=loc[K];
	for(i=1;i<=N;i++)
	{
		loc[i]-=st;
	}
	L temp=bin(0,1000000001);
	printf("%lld",temp);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:165:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&N,&K,&T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&loc[i]);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 560 KB Output is correct
7 Incorrect 2 ms 560 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 560 KB Output is correct
7 Incorrect 2 ms 560 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 560 KB Output is correct
7 Incorrect 2 ms 560 KB Output isn't correct
8 Halted 0 ms 0 KB -