Submission #514769

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <string>
#include <queue>
#include <functional>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <string.h>
using namespace std;

namespace{
	#define		CAST( T, val )		( (T)( val ) )
	#define		CASE( lb )			break; case lb:
	#define		CASE_CONTINUE( lb )	case lb:
	#define		CASE_DEFAULT		break; default:
	#define		For( i, s )			for(int i= 0; i< (int)s; i++)
	#define		ForA( i, a, s )		for(int i= (int)a; i< (int)s; i++)
	#define		ForSize( i, s )		for(int i= 0, size= (int)s; i< size; i++)
	#define		ForSizeA( i, a, s )	for(int i= (int)a, size= (int)s; i< size; i++)
	#define		ForItr( itr, con )	for(auto itr= con.begin(); itr!= con.end(); itr++)
	#define		ForStr( i, str )	for(int i= 0; str[i]; i++)
	#define		GOTO( lb )			goto lb
	#define		LABEL( lb )			lb:
	#define		ALL( con )			con.begin(), con.end()

	typedef		long long		LLint;
	typedef		unsigned int	Uint;
	typedef		unsigned char	Uchar;
	typedef		unsigned short	Ushort;

	const int Ten5 = 100000;		//	10^5
	const int Ten6 = 1000000;	//	10^6
	const double EPS = 0.00000000023283064365386962890625;	//	2^-32
	template <typename T> class priority_queue_less : public priority_queue < T, vector<T>, greater<T> > {};
}


bool isCanClear(const int N, const int t, const int* L, const int R)
{
	int r= 0;
	For( n, N ){
		const int l= max( L[n]-r, 0 );
		if( l > t ) return false;

		r= max( t-2*l, ( t-l ) >> 1 );
	}

	return r>=R;
}
int main()
{
	int N, L[Ten5], R;
	LLint T;
	cin>> T>> N;
	
	int M, p= 0;
	For( n, N ){
		cin>> M;
		L[n]= M-p-1;
		p= M;
	}
	R= T-M;
	T= T/2*3+1;

	LLint bot= 0, top= T;
	while(1){
		if( top <= bot ) break;
		const LLint mid= ( top +bot ) >> 1;

		if( isCanClear( N, mid, L, R ) ){
			top= mid;
		}else{
			bot= mid+1;
		}
	}

	cout<< bot<< endl;

	return 0;
}

Submission Info

Judge Result