Submission #3894888


Source Code Expand

Copy
#include "bits/stdc++.h" // {{{
using namespace std; typedef long long ll; typedef pair<int,int> pii;
#define LF          '\n'
#define val         const auto
#define eb          emplace_back
#define emp         emplace
#define fi          first
#define se          second
#define outl(x)     cout << (x) << '\n'
#define rep(i,n)    for(int i=0; i < (int)(n); ++i)
#define repr(i,h,l) for(int i=(h); i >= (int)(l); --i)
#define reps(i,s,t) for(int i=(s); i <= (int)(t); ++i)
#define ALL(x)      begin(x), end(x)
#define UNQ(x)      (x).erase(std::unique(ALL(x)), end(x))
#define TMPLT(T,U)  template<class T, class U>
#define ten(p)      ((long long)(1e##p))
#define FILL(a,v)   memset((a), (v), sizeof(a))
#define YDK(f,a,b)  ((f)? (a):(b))
#ifdef  DEBUG
#define debug(...)  fprintf(stderr, __VA_ARGS__)
#define show(x)     clog << #x << " \t\t= " << (x) << '\n'
#define show2(x,y)  clog << '(' << #x << ',' << #y << ")\t\t= " << '(' << (x) << "\t, " << (y) << ")\n"
#define LN()        fputs("\n--------------------------------\n", stderr)
struct NullPointer{};
#else
#define debug(...)
#define show(x)
#define show2(x,y)
#define LN()
struct NullPointer{ NullPointer(){cin.tie(0);ios::sync_with_stdio(false);} };
#endif
#define def(op) inline bool operator op (const T &that) const { return comp(that) op 0; }
template<class T> struct Ordered
{ virtual int comp(const T &that) const = 0; def(==); def(!=); def(<); def(<=); def(>); def(>=); };
#undef def
namespace {
  constexpr int INF = 0x3f3f3f3f; constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL; ostringstream _oss;
  TMPLT(T,U) inline constexpr common_type_t<T,U> gcd(T x, U y)
  { return (x<y)? gcd(y,x) : (y <= 0)? x : gcd(y, x % y); }
  TMPLT(T,U) inline bool chmax(T &a, const U &b){return b>a ? a=b,1 : 0;}
  TMPLT(T,U) inline bool chmin(T &a, const U &b){return b<a ? a=b,1 : 0;}
  TMPLT(T,U) inline constexpr ll lcm(T x, U y) { return (ll)x/gcd(x,y) * y; }
  template<class T>   string toString(const T &x){ _oss.str(""); _oss << x; return _oss.str(); }
  template<class Itr> string mkString(Itr begin, Itr end, const char *sp = " ") {
    _oss.str(""); for(Itr i=begin; i != end; ++i) { if(i != begin)_oss << sp; _oss << *i; }
    return _oss.str();
  }
  // }}}

constexpr int MX = 2 * ten(5) + 10;

long L;
long x[MX];
long y[MX];
long dp[8002][8002][2];
int N;

long slv(int left, int right, bool nowLeft)
{
  if (left + right >= N) { return 0; }

  if (left > 8000 || right > 8000)
  {
    long ret = 0;
    //toLeft
    if (nowLeft) {
      chmax(ret, slv(left+1, right, true) + (x[left+1] - x[left]) );
    } else {
      chmax(ret, slv(left+1, right, true) + y[right] + x[left+1]);
    }

    // toRight
    if (nowLeft) {
      chmax(ret, slv(left, right+1, false) + x[left] + y[right+1]);
    } else {
      chmax(ret, slv(left, right+1, false) + (y[right+1] - y[right]) );
    }

    return ret;
  }
  else
  {
    long &ret = dp[left][right][nowLeft];
    if (~ret) { return ret; }

    ret = 0;

    // toLeft
    if (nowLeft) {
      chmax(ret, slv(left+1, right, true) + (x[left+1] - x[left]) );
    } else {
      chmax(ret, slv(left+1, right, true) + y[right] + x[left+1]);
    }

    // toRight
    if (nowLeft) {
      chmax(ret, slv(left, right+1, false) + x[left] + y[right+1]);
    } else {
      chmax(ret, slv(left, right+1, false) + (y[right+1] - y[right]) );
    }

    return ret;
  }
}

void Xx_main_xX(const vector<char*> &args)
{
  cin >> L >> N;
  for (int i = 1; i <= N; ++i) {
    cin >> x[i];
    y[N-i + 1] = L - x[i];
  }

  FILL(dp, -1);

  long toLeft = slv(1, 0, true) + x[1];
  long toRight = slv(0, 1, false) + y[1];

  outl( max(toLeft, toRight) );

}

} // {{{
signed main(signed argc, char *argv[]) {
  NullPointer Exception;
  cout << fixed << setprecision(9); Xx_main_xX(vector<char*>(argv, argv+argc)); return 0;
} // }}}

Submission Info

Submission Time
Task B - Tree Burning
User YDK_NK
Language C++14 (GCC 5.4.1)
Score 300
Code Size 3953 Byte
Status
Exec Time 2107 ms
Memory 1019520 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
Subtask1 300 / 300 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 39.txt, 40.txt, s1.txt, s2.txt, s3.txt
All 0 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 286 ms 1003904 KB
02.txt 285 ms 1003904 KB
03.txt 286 ms 1003904 KB
04.txt 286 ms 1003904 KB
05.txt 285 ms 1003904 KB
06.txt 286 ms 1003904 KB
07.txt 285 ms 1003904 KB
08.txt 286 ms 1003904 KB
09.txt 285 ms 1003904 KB
10.txt 285 ms 1003904 KB
11.txt 286 ms 1003904 KB
12.txt 285 ms 1003904 KB
13.txt 286 ms 1003904 KB
14.txt 286 ms 1003904 KB
15.txt 285 ms 1003904 KB
16.txt 285 ms 1003904 KB
17.txt 286 ms 1003904 KB
18.txt 285 ms 1003904 KB
19.txt 285 ms 1003904 KB
20.txt 286 ms 1003904 KB
21.txt 286 ms 1003904 KB
22.txt 285 ms 1003904 KB
23.txt 286 ms 1003904 KB
24.txt 286 ms 1003904 KB
25.txt 2107 ms 1019520 KB
26.txt 2107 ms 1019520 KB
27.txt 2107 ms 1019520 KB
28.txt 2107 ms 1019520 KB
29.txt 2107 ms 1019520 KB
30.txt 2107 ms 1019520 KB
31.txt 2107 ms 1019520 KB
32.txt 2107 ms 1019520 KB
33.txt 2107 ms 1019520 KB
34.txt 2107 ms 1019520 KB
35.txt 2107 ms 1019520 KB
36.txt 2107 ms 1019520 KB
37.txt 2107 ms 1019520 KB
38.txt 2107 ms 1019520 KB
39.txt 243 ms 1003776 KB
40.txt 243 ms 1003776 KB
s1.txt 243 ms 1003776 KB
s2.txt 243 ms 1003776 KB
s3.txt 243 ms 1003776 KB