Submission #18999317


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


int root(int[] uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u]));
}
bool connect(int[] uf, int u, int v) {
  u = uf.root(u);
  v = uf.root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


enum INF = 10^^9;

int solve(const(int[]) A) {
  const N = cast(int)(A.length);
  auto ASum = new int[N + 1];
  foreach (i; 0 .. N) {
    ASum[i + 1] = ASum[i] + A[i];
  }
  auto dpMin = new int[][](N + 1, N + 1);
  auto dpMax = new int[][](N + 1, N + 1);
  foreach (i; 0 .. N + 1) {
    dpMin[i][i] = dpMax[i][i] = 0;
  }
  foreach (w; 1 .. N + 1) {
    foreach (i; 0 .. N - w + 1) {
      const j = i + w;
      dpMin[i][j] = +INF;
      dpMax[i][j] = -INF;
      chmin(dpMin[i][j], dpMin[i + 1][j]);
      chmax(dpMax[i][j], dpMax[i + 1][j]);
      chmin(dpMin[i][j], dpMin[i][j - 1]);
      chmax(dpMax[i][j], dpMax[i][j - 1]);
      foreach (k; i + 1 .. j) {
        chmin(dpMin[i][j], dpMin[i][k] + dpMin[k][j]);
        chmax(dpMax[i][j], dpMax[i][k] + dpMax[k][j]);
      }
      if (w % 3 == 0) {
        chmin(dpMin[i][j], (ASum[j] - ASum[i]) - dpMax[i][j]);
        chmax(dpMax[i][j], (ASum[j] - ASum[i]) - dpMin[i][j]);
      }
    }
  }
  return dpMax[0][N];
}

void main() {
  debug {
    foreach (n; 3 .. 16 + 1) {
      auto uf = new int[1 << n];
      uf[] = -1;
      foreach (u; 0 .. 1 << n) {
        foreach (i; 0 .. n - 3 + 1) {
          const du = 7 << i;
          if (!(u & du) || !(~u & du)) {
            uf.connect(u, u ^ du);
          }
        }
      }
      stderr.writeln(n, ": ", -uf[uf.root(0)]);
      stderr.flush;
      foreach (u; 0 .. 1 << n) {
        if (uf.root(0) == uf.root(u)) {
          /*
          foreach (i; 0 .. n) {
            write((u >> i) & 1);
          }
          writeln;
          */
          {
            auto as = new int[n];
            foreach (i; 0 .. n) {
              as[i] = ((u >> i) & 1) ? +1 : -1;
            }
            const res = solve(as);
            assert(popcnt(u) == res, format("%s: %s", as, res));
          }
        }
      }
    }
  }
  
  try {
    for (; ; ) {
      const N = readInt();
      auto A = new int[N];
      foreach (i; 0 .. N) {
        A[i] = readInt();
      }
      
      const ans = solve(A);
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task B - Three Coins
User hos_lyric
Language D (LDC 1.20.1)
Score 800
Code Size 3630 Byte
Status AC
Exec Time 106 ms
Memory 5292 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 49
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 106 ms 5136 KB
001.txt AC 101 ms 5244 KB
002.txt AC 100 ms 5224 KB
003.txt AC 101 ms 5284 KB
004.txt AC 101 ms 5172 KB
005.txt AC 103 ms 5160 KB
006.txt AC 99 ms 5108 KB
007.txt AC 97 ms 5228 KB
008.txt AC 100 ms 5212 KB
009.txt AC 102 ms 5164 KB
010.txt AC 98 ms 5164 KB
011.txt AC 100 ms 5132 KB
012.txt AC 100 ms 5188 KB
013.txt AC 101 ms 5188 KB
014.txt AC 100 ms 5172 KB
015.txt AC 100 ms 5172 KB
016.txt AC 100 ms 5164 KB
017.txt AC 101 ms 5164 KB
018.txt AC 100 ms 5160 KB
019.txt AC 102 ms 5140 KB
020.txt AC 100 ms 5200 KB
021.txt AC 103 ms 5112 KB
022.txt AC 103 ms 5076 KB
023.txt AC 103 ms 5164 KB
024.txt AC 102 ms 5212 KB
025.txt AC 102 ms 5256 KB
026.txt AC 102 ms 5204 KB
027.txt AC 102 ms 5148 KB
028.txt AC 103 ms 5204 KB
029.txt AC 102 ms 5128 KB
030.txt AC 102 ms 5084 KB
031.txt AC 102 ms 5268 KB
032.txt AC 98 ms 5184 KB
033.txt AC 100 ms 5188 KB
034.txt AC 100 ms 5180 KB
035.txt AC 101 ms 5292 KB
036.txt AC 101 ms 5080 KB
037.txt AC 102 ms 5184 KB
038.txt AC 101 ms 5192 KB
039.txt AC 99 ms 5224 KB
040.txt AC 103 ms 5208 KB
041.txt AC 102 ms 5064 KB
042.txt AC 102 ms 5100 KB
043.txt AC 99 ms 5156 KB
044.txt AC 101 ms 5096 KB
045.txt AC 100 ms 5280 KB
example0.txt AC 3 ms 3280 KB
example1.txt AC 3 ms 3232 KB
example2.txt AC 3 ms 3296 KB