Submission #3766416

---

Source Code Expand

import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
  return array(map!(to!int)(readln().strip().split()));
}

auto readInt() {
  return readInts()[0];
}

auto readLongs() {
  return array(map!(to!long)(readln().strip().split()));
}

auto readLong() {
  return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
  auto s = readln().split();
  assert(s.length == t.length);
  foreach (ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1 .. $];
  }
}

class UnionFindTree {
public:
  this(size_t n) {
    parent = iota(n).array();
    rank = new size_t[](n);
  }

  size_t find(size_t n) {
    if (n == parent[n]) {
      return n;
    } else {
      parent[n] = find(parent[n]);
      return parent[n];
    }
  }

  void unite(size_t n, size_t m) {
    auto p1 = find(n);
    auto p2 = find(m);
    if (n == m) {
      return;
    }
    if (rank[p1] < rank[p2]) {
      swap(p1, p2);
    }
    if (rank[p1] == rank[p2]) {
      ++rank[p1];
    }
    parent[p2] = p1;
  }

private:
  size_t[] parent;
  size_t[] rank;
}

unittest {
  auto uft = new UnionFindTree(10);
  foreach (i; iota(10)) {
    assert(uft.find(i) == i);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0).drop(1)) {
    uft.unite(i, i - 3);
  }
  foreach (i; iota(10).filter!(a => a % 3 == 0)) {
    assert(uft.find(0) == uft.find(i));
  }
  foreach (i; iota(10).filter!(a => a % 3 != 0)) {
    assert(uft.find(0) != uft.find(i));
  }
}

//内部では1-based, 使うときは0-based
class BinaryIndexedTree(T, alias F = "a + b") if (is(typeof(binaryFun!F))) {
  alias f = binaryFun!F;
public:
  this(in size_t n, in T T0 = T.init) {
    t.length = n + 1;
    t[] = T0;
  }

  void add(in size_t idx, in T v)
  in {
    assert(idx < t.length - 1);
  }
  body {
    one_based_add(idx + 1, v);
  }

  T accumulate(size_t idx) {
    return one_based_accumulate(idx + 1);
  }

private:
  T[] t;

  //1-based
  void one_based_add(size_t idx, in ref T v) {
    if (idx >= t.length) {
      return;
    }
    t[idx] = f(t[idx], v);
    one_based_add(idx + (idx & (-idx)), v);
  }

  T one_based_accumulate(size_t idx) {
    if (idx == 0) {
      return t[0];
    } else {
      return f(one_based_accumulate(idx - (idx & (-idx))), t[idx]);
    }
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long)(10);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 0);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 0);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 5);
  }
}

unittest {
  auto bit = new BinaryIndexedTree!(long, "a*b")(10, 1);
  foreach (i; iota(10)) {
    assert(bit.accumulate(i) == 1);
  }
  bit.add(5, 3);
  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 10)) {
    assert(bit.accumulate(i) == 3);
  }

  bit.add(7, 2);

  foreach (i; iota(5)) {
    assert(bit.accumulate(i) == 1);
  }
  foreach (i; iota(5, 7)) {
    assert(bit.accumulate(i) == 3);
  }
  foreach (i; iota(7, 10)) {
    assert(bit.accumulate(i) == 6);
  }
}

//最大流、O(|V||E|^2)
template Flow_Dinic() {
  class Edge {
  public:
    this(long to, long capacity) {
      this.to = to;
      this.capacity = capacity;
    }

    long to;
    long capacity;
    Edge reverse;
  }

  //gを残余グラフにする
  void residualise(ref Edge[][] g) {
    foreach (u; iota(g.length)) {
      foreach (e; g[u]) {
        if (e.capacity != 0) {
          e.reverse = new Edge(u, 0);
          e.reverse.reverse = e;
          g[e.to] ~= e.reverse;
        }
      }
    }
  }

  const long INF = long.max / 2;

  //gは残余グラフ
  //gは計算の結果書き換わる
  long solve(Edge[][] g, long s, long t) {
    long ret;
    while (true) {
      auto level = new long[](g.length);
      level[] = INF;
      auto q = DList!long(s);
      level[s] = 0;
      //level graph
      auto lg = new Edge[][](g.length, 0);
      while (!q.empty()) {
        auto u = q.front();
        q.removeFront();
        if (u == t) {
          break;
        }
        foreach (e; g[u]) {
          if (e.capacity > 0 && level[e.to] >= level[u] + 1) {
            level[e.to] = level[u] + 1;
            q.insertBack(e.to);
            lg[u] ~= e;
          }
        }
      }
      if (level[t] == INF) {
        break;
      }
      auto iter = new long[](g.length);
      long dfs(long u, long c_min) {
        if (u == t) {
          return c_min;
        }
        foreach (i; iota(iter[u], lg[u].length)) {
          iter[u] = i;
          long f = dfs(lg[u][i].to, min(c_min, lg[u][i].capacity));
          if (f > 0) {
            lg[u][i].capacity -= f;
            lg[u][i].reverse.capacity += f;
            return f;
          }
        }
        return 0;
      }

      while (true) {
        long f = dfs(s, INF);
        if (f == 0) {
          break;
        }
        ret += f;
      }
    }
    return ret;
  }
}

enum real eps = 1e-10;

enum long mod = 1_000_000_000 + 7;

void main() {
  auto n = readLong();
  long[] a, b;
  foreach(i; iota(n)) {
    long ai, bi;
    readlnTo(ai, bi);
    a ~= ai;
    b ~= bi;
  }
  if(zip(a, b).all!(a => a[0] == a[1])) {
    writeln(0);
    return;
  }
  long m = long.max;
  foreach(i; iota(n)) {
    if(a[i] > b[i]) {
      m = min(m, b[i]);
    }
  }
  writeln(a.sum() - m);
}

Submission Info

Judge Result