Submission #980058

---

Source Code Expand

// default code for competitive programming
// ver 3.1415 {{{

// Includes
#include <bits/stdc++.h>

// Defines
#define NAME(x) #x
#define SZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define FOR(i, e) for( int i = 0 ; i < (e) ; i++ )
#define ITER(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define REP(i, s, e) for(int i = (s); i <= (e); i++)
#define REPD(i, s, e) for(int i = (s); i >= (e); i--)
#define IOS ios_base::sync_with_stdio( 0 )
#define DEBUG 1
#define fst first
#define snd second
#define PB push_back
#ifdef ONLINE_JUDGE
#define FILE( fn ) \
    freopen(fn".in","r",stdin); \
freopen(fn".out","w",stdout);
#else
#define FILE( fn )
#endif

#ifdef AKAI
#define debug( ... ) fprintf( stderr , __VA_ARGS__ )
#else
#define debug( ... )
#endif

using namespace std;

// Typedefs
typedef double real;
typedef long long ll;
typedef pair<ll, int> pli;
typedef tuple<ll, int> tli;
typedef pair<int, int> pii;
typedef tuple<int, int> tii;
typedef unsigned long long ull;

// Some common const.
const double EPS = 1e-8;
const double Pi = acos(-1);

// Equal for double
bool inline equ(double a, double b)
{return fabs(a - b) < EPS;}

int _R( int& x ) { return scanf( "%d" , &x ); }
int _R( ll& x ) { return scanf( "%" PRId64 , &x ); }
int _R( double& x ) { return scanf( "%lf" , &x ); }
int _R( char* s ) { return scanf( "%s" , s ); }

int R() { return 0; }

  template< typename T1 , typename... T2 >
int R( T1& x , T2&... tail )
{
  int tmp = _R( x );
  return tmp + R( tail... );
}

  template< typename Iter , typename F >
inline void out( Iter s , Iter e , F of )
{
  bool flag = 0;
  for( Iter it = s ; it != e ; it++ )
  {
    if( flag ) printf( " " );
    else flag = 1;
    of( *it );
  }
  puts( "" );
}

// }}}
// start ~~QAQ~~

const int MAXN = 1e5+10;
const ll  INF  = 1000000000000000;

int n;
ll E , T;
ll x[ MAXN ];
ll dp[ MAXN ] , mn[ MAXN ];

inline ll f( int i ) {
  return T+dp[ i ]-x[ i ];
}

inline ll g( int i ) {
  return dp[ i ]-x[ i ]-2*x[ i+1 ];
}

int main() {
  R( n , E , T );
  REP( i , 1 , n ) R( x[ i ] );
  dp[ 0 ] = 0;
  deque<int> dq{ 0 };
  int j = 0;
  mn[ 0 ] = g( 0 );
  REP( i , 1 , n ) {
    while( SZ( dq ) && 2*x[ dq.front()+1 ] < 2*x[ i ]-T )
      dq.pop_front();
    while( j < i && 2*x[ j+1 ] < 2*x[ i ]-T ) j++;
    dp[ i ] = INF;
    if( SZ( dq ) ) dp[ i ] = x[ i ] + f( dq.front() );
    if( j > 0 ) dp[ i ] = min( dp[ i ] , 3*x[ i ] + mn[ j-1 ] );
    //printf( "%lld dp %d %lld j %d\n" , x[ i ] , i , dp[ i ] , j );
    while( SZ( dq ) && f( dq.back() ) >= f( i ) )
      dq.pop_back();
    dq.push_back( i );
    mn[ i ] = min( mn[ i-1 ] , g( i ) );
  }
  printf( "%lld\n" , dp[ n ] + E-x[ n ] );
}

Submission Info

Compile Error

./Main.cpp: In function ‘int _R(ll&)’:
./Main.cpp:55:49: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘ll* {aka long long int*}’ [-Wformat=]
 int _R( ll& x ) { return scanf( "%" PRId64 , &x ); }
                                                 ^

Judge Result