ZJP2016

ZJP2016_A.cc

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T; cin >> T;
  for (int _ = 0; _ < T; ++_ ) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << c << " " << b + d << endl;
    cout << a << " " << b + d << endl;
  }
  return 0;
}

ZJP2016_B.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

class Solution {
  static const int MAXN = 100000 + 10;
  static const LL inf = 1ll << 60;
  vector<int> G[MAXN];
  int w[MAXN], n;

  struct Line {// m * x + b
    LL m, b;
    double inter(const Line &r) const {
      return (r.b - b) / (m - r.m);
    }
    inline LL eval(LL x) {return m * x + b;}
  } Q[MAXN];

  int rt, mins, total, top;
  int vs[MAXN], sz[MAXN], dep[MAXN];
  LL val[MAXN], ps[MAXN], ret;

  void getCenter(int u, int f = -1) {
    int mx = 0; sz[u] = 1;
    for (auto &v: G[u]) if (v != f && !vs[v]) {
      getCenter(v, u); sz[u] += sz[v];
      mx = max(mx, sz[v]);
    }
    mx = max(mx, total - sz[u]);
    if (mx < mins) mins = mx, rt = u;
  }
  int dfs1(int u, int d = 1) {
    ret = max(ret, val[d]);
    for (auto &v: G[u]) if (!vs[v] && u > v) {
      ps[v] = ps[u] + w[v];
      val[d + 1] = val[d] + ps[v];
      return dfs1(v, d + 1) + 1;
    }
    return 1;
  }
  void dfs2(int u, int d = 0, LL sum = 0) {
    sum += 1ll * d * w[u];
    // max(ps[u] * m + b + sum)
    int left = 0, right = top - 2;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (Q[mid].eval(ps[u]) >= Q[mid + 1].eval(ps[u])) right = mid;
      else left = mid + 1;
    }
    ret = max(ret, Q[left].eval(ps[u]) + sum);
    if (left + 1 < top) ret = max(ret, Q[left + 1].eval(ps[u]) + sum);
    for (auto &v: G[u]) if (!vs[v] && u < v) {
      ps[v] = ps[u] + w[v];
      dfs2(v, d + 1, sum);
    }
  }
  void solve(int u, int _tot) {
    total = _tot; mins = _tot * 2;
    getCenter(u); u = rt; vs[u] = 1; getCenter(u);
    val[1] = ps[u] = w[u];
    int md = dfs1(u);
    top = 0;
    for (int i = 1; i <= md; ++i) {
      Line now = (Line){i, val[i]};
      while (top >= 2 && Q[top - 2].inter(Q[top - 1]) >= Q[top - 1].inter(now)) --top;
      Q[top++] = now;
    }
    ps[u] = 0; dfs2(u);
    for (int i = 0; i <= md; ++i) val[i] = -inf;
    for (auto &v: G[u]) if (!vs[v]) {
      solve(v, sz[v]);
    }
  }

public:
  void run() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", w + i); G[i].clear();
    }
    for (int i = 1; i < n; ++i) {
      int x; scanf("%d", &x); --x;
      G[x].push_back(i);
      G[i].push_back(x);
    }
    ret = 0;
    for (int i = 0; i < n; ++i) val[i] = -inf;
    memset(vs, 0, sizeof(vs[0]) * n);
    solve(0, n);
    printf("%lld\n", ret);
  }
} sol;

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) sol.run();
  return 0;
}

ZJP2016_C.cc

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

vector<PII> res;
int b[5][5], a[5];

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    int r[5];
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        cin >> b[i][j];
      }
    }
    // stage 1
    int *x = b[0], d = x[0];
    if (d <= 2) r[0] = 2;
    else r[0] = d;
    // stage 2
    x = b[1], d = x[0];
    for (int i = 1; i < 5; ++i) a[x[i]] = i;
    if (d == 1) r[1] = a[4];
    else if (d == 3) r[1] = 1;
    else r[1] = r[0];
    // stage 3
    x = b[2], d = x[0];
    for (int i = 1; i < 5; ++i) a[x[i]] = i;
    if (d == 1) r[2] = a[b[1][r[1]]];
    else if (d == 2) r[2] = a[b[0][r[0]]];
    else if (d == 4) r[2] = a[4];
    else r[2] = d;
    // stage 4
    x = b[3], d = x[0];
    if (d == 1) r[3] = r[0];
    else if (d == 2) r[3] = 1;
    else r[3] = r[1];
    // stage 5
    x = b[4], d = x[0];
    for (int i = 1; i < 5; ++i) a[x[i]] = i;
    if (d <= 2) r[4] = a[b[d - 1][r[d - 1]]];
    else r[4] = a[b[6 - d][r[6 - d]]];
    for (int i = 0; i < 5; ++i) {
      cout << r[i] << " " << b[i][r[i]] << endl;
    }
  }
  return 0;
}

ZJP2016_D.cc

#include <bits/stdc++.h>
using namespace std;

vector<tuple<int, int, int>> p;

int day(int y, int m, int d) {
  int tm = m >= 3 ? (m - 2) : (m + 10);
  int ty = m >= 3 ? y : (y - 1);
  return (ty + ty / 4 - ty / 100 + ty / 400 + (int)(2.6 * tm - 0.2) + d) % 7;
}

void run() {
  int y, m, d, n; cin >> y >> m >> d >> n;
  y -= 1753; n += y / 2800 * p.size();
  y %= 2800;
  n += lower_bound(p.begin(), p.end(), make_tuple(y, m, d)) - p.begin() - 1;
  auto res = p[n % p.size()];
  y = get<0>(res);
  m = get<1>(res);
  d = get<2>(res);
  y += n / p.size() * 2800 + 1753;
  cout << y << " " << m << " " << d << endl;
}

int main() {
  cerr << day(1753, 1, 1) << endl;
  for (int y = 0; y < 2800; ++y) {
    for (int m = 1; m <= 12; ++m) {
      if (day(y + 1753, m,  1) == 1) p.push_back(make_tuple(y, m,  1));
      if (day(y + 1753, m, 11) == 1) p.push_back(make_tuple(y, m, 11));
      if (day(y + 1753, m, 21) == 1) p.push_back(make_tuple(y, m, 21));
    }
  }
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) run();
  return 0;
}

ZJP2016_E.cc

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10, M = 1e9 + 7;
int a[MAXN], n, m;
map<int, int> last;

void run() {
  scanf("%d%d", &n, &m);
  last.clear(); last[m] = 1;
  for (int i = 0; i < n; ++i) {
    int x, s = 0; scanf("%d", &x);
    auto it = last.lower_bound(x);
    for (; it != last.end(); ) {
      last[it->first % x] += it->second;
      s += it->second * (it->first / x);
      it = last.erase(it);
    }
    if (s) last[x - 1] += s;
  }
  int s = 0;
  for (auto it = last.rbegin(); it != last.rend(); ++it) {
    it->second += s; s = it->second;
  }
  int q, ret = 0; scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int x; scanf("%d", &x);
    auto it = last.lower_bound(x);
    if (it != last.end()) ret += 1ll * it->second * i % M;
    if (ret >= M) ret -= M;
  }
  printf("%d\n", ret);
}

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) run();
  return 0;
}

ZJP2016_F.cc

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 100 + 10;

PII P[MAXN];
int n, m, k;

void run() {
  cin >> n >> k >> m;
  for (int i = 0; i < n; ++i) {
    cin >> P[i].first >> P[i].second;
  }
  sort(P, P + n);
  int s = 0, ret = 0;
  for (int i = 1; i < n; ++i) {
    if (P[i].first <= P[s].second + 1) {
      P[s].second = max(P[s].second, P[i].second);
    } else P[++s] = P[i];
  }
  n = s + 1; s = 1 << n;
  for (int msk = 0; msk < s; ++msk) {
    int sum = 0, now = 0, rest = m;
    for (int i = 0; i < n && rest; ++i) {
      now = max(now, P[i].first - 1);
      if (now >= P[i].second && (msk >> i & 1)) {
        sum += P[i].second + k - 1 - now;
        now = P[i].second + k - 1;
        rest--;
      } else if (now < P[i].second) {
        int t = min(rest, (P[i].second - now - 1) / k + 1);
        sum += t * k; now += t * k; rest -= t;
        assert(now >= P[i].second || rest == 0);
        if (rest && (msk >> i & 1)) {
          sum += P[i].second + k - 1 - now;
          now = P[i].second + k - 1;
          rest--;
        }
      }
    }
    ret = max(ret, sum);
  }
  cout << ret << endl;
}

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) run();
  return 0;
}

ZJP2016_G.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VP;

class Solution {
  static const int MAXN = 2000 + 10;
  int a[MAXN], n, m;
  LL count00(LL ret = 0) {
    map<VI, VP> mp;
    for (int i = 1; i < n; i += 2) {
      VI pt; int sum = 0;
      for (int j = i; j + 1 < n; ++j) {
        pt.push_back(a[j]);
        if (j & 1) {
          if (a[i - 1] + sum + a[j + 1] >= m) {
            mp[pt].push_back(PII(a[i - 1], a[j + 1]));
          }
        } else sum += a[j];
        if (sum >= m) break;
      }
    }
    for (auto &e: mp) {
      VP &y = e.second, x;
      int sum = m;
      for (size_t i = 1; i < e.first.size(); i += 2) sum -= e.first[i];
      for (auto &v: y) {
        int L = v.first, R = v.second;
        v.first = max(1, sum - R);
        v.second = min(L, sum - 1);
        if (v.first <= v.second) x.push_back(v);
      }
      if (x.empty()) continue;
      sort(x.begin(), x.end());
      int l = x[0].first, r = x[0].second;
      for (size_t i = 0; i < x.size(); ++i) {
        if (x[i].first <= r) r = max(r, x[i].second);
        else {
          ret += r - l + 1;
          l = x[i].first;
          r = x[i].second;
        }
      }
      ret += r - l + 1;
    }
    return ret;
  }
  LL count10(LL ret = 0) {
    map<VI, int> mp;
    for (int i = 1; i < n; i += 2) {
      VI pt; int sum = 0;
      for (int j = i + 1; j < n; ++j) {
        pt.push_back(a[j]);
        if (~j & 1) {
          sum += a[j];
          if (sum >= m) {
            sum -= a[j];
            pt.pop_back();
            pt.push_back(m - sum);
            mp[pt] = max(mp[pt], a[i]);
            break;
          }
        }
      }
    }
    for (auto &e: mp) ret += e.second;
    return ret;
  }
  LL count11(LL ret = 0) {
    map<VI, VP> mp;
    for (int i = 2; i < n; i += 2) {
      VI pt; int sum = 0;
      for (int j = i; j + 1 < n; ++j) {
        pt.push_back(a[j]);
        if (~j & 1) {
          sum += a[j];
          if (sum == m) mp[pt].push_back(PII(a[i - 1], a[j + 1]));
          else if (sum > m) break;
        }
      }
    }
    for (auto &e: mp) {
      VP &y = e.second;
      sort(y.begin(), y.end());
      for (int i = y.size() - 2; i >= 0; --i) {
        y[i].second = max(y[i].second, y[i + 1].second);
      }
      for (size_t i = 0; i < y.size(); ++i) {
        int extra = i ? y[i].first - y[i - 1].first : y[i].first;
        ret += 1ll * extra * y[i].second;
      }
    }
    return ret;
  }
public:
  void run() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    LL ret = count00() + count11();
    ret += count10();
    if (n % 2 == 0) a[n++] = 0;
    reverse(a, a + n);
    ret += count10();
    for (int i = 0; i < n; i += 2) if (a[i] >= m && m) {
      ++ret; break;
    }
    if (m == 0) {
      ret = 0;
      for (int i = 1; i < n; i += 2) ret = max(ret, (LL)a[i]);
    }
    printf("%lld\n", ret);
  }
} sol;

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) sol.run();
  return 0;
}

ZJP2016_H.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

class Solution {
  static const int MAXN = 100000 + 10;
  static const LL inf = 1ll << 60;
  int a[MAXN], n, q, ret;
  bool mark[MAXN];
  set<int> eq;

  struct BIT {
    LL u[MAXN];
    int n;
    void clr(int _n) {
      n = _n;
      memset(u, 0, sizeof(u[0]) * (n + 1));
    }
    void add(int x, LL v) {
      for (; x <= n; x += ~x & x + 1) u[x] += v;
    }
    void add(int l, int r, LL v) {//[l, r]
      add(l, v); add(r + 1, -v);
    }
    LL get(int x, LL r = 0) {//[0,x]
      for (; x >= 0; x -= ~x & x + 1) r += u[x];
      return r;
    }
  } bit;

  struct SegTree {
    #define lson (rt<<1)
    #define rson (rt<<1|1)
    #define mid ((l+r)>>1)
    struct Node {
      LL val, add;
      int idx;
      void mark(LL v) {
        val += v; add += v;
      }
    } T[MAXN << 2];
    void upd(int rt) {
      T[rt].val = max(T[lson].val, T[rson].val);
      if (T[rt].val == T[lson].val) T[rt].idx = T[lson].idx;
      else T[rt].idx = T[rson].idx;
    }
    void psd(int rt) {
      T[lson].mark(T[rt].add);
      T[rson].mark(T[rt].add);
      T[rt].add = 0;
    }
    void build(int rt, int l, int r) {
      T[rt].add = 0; T[rt].val = -inf; T[rt].idx = l;
      if (l + 1 == r) return;
      build(lson, l, mid);
      build(rson, mid, r);
    }
    void ins(int rt, int l, int r, int x, LL v) {
      if (l + 1 == r) {T[rt].val = v; return;}
      psd(rt);
      if (x < mid) ins(lson, l, mid, x, v);
      else ins(rson, mid, r, x, v);
      upd(rt);
    }
    void add(int rt, int l, int r, int L, int R, LL v) {
      if (L <= l && R >= r) {T[rt].mark(v); return;}
      psd(rt);
      if (L < mid) add(lson, l, mid, L, R, v);
      if (R > mid) add(rson, mid, r, L, R, v);
      upd(rt);
    }
    const Node& Max() const {return T[1];}
  } st;

public:
  void run() {
    scanf("%d%d", &n, &q); ret = 0;
    for (int i = 0; i < n; ++i) scanf("%d", a + i);
    st.build(1, 0, n); bit.clr(n);
    eq.clear(); a[n] = 0;
    memset(mark, 0, sizeof(mark));
    for (int i = n - 1; i > 0; --i) {
      a[i] -= a[i - 1];
      if (a[i] == 0) eq.insert(i);
      if (a[i] < 0) st.ins(1, 0, n, i, a[i]);
      if (a[i] > 0 && a[i + 1] < 0) ++ret;
      bit.add(i, i, a[i]);
    }
    cerr << ret << std::endl;
    for (int i = 0; i < q; ++i) {
      int l, r, a, b; scanf("%d%d%d%d", &l, &r, &a, &b);
      LL cl = a, cr = a + 1ll * b * (r - l); --l;
      vector<int> pt;
      st.ins(1, 0, n, l, -inf); eq.erase(l);
      if (l) pt.push_back(l);
      if (l < r - 1) {
        for (auto it = eq.lower_bound(l); it != eq.end(); it = eq.erase(it)) {
          if (*it >= r) break; pt.push_back(*it);
        }
        st.add(1, 0, n, l + 1, r, b);
        while (st.Max().val >= 0) {
          pt.push_back(st.Max().idx);
          st.ins(1, 0, n, pt.back(), -inf);
        }
      }
      if (r < n) {
        st.ins(1, 0, n, r, -inf);
        eq.erase(r);
        pt.push_back(r);
      }
      for (auto &x: pt) mark[x] = true;
      for (auto &x: pt) {
        LL v = bit.get(x);
        if (x > 1 && v < 0 && bit.get(x - 1) > 0) --ret;
        if (x + 1 < n && v > 0 && bit.get(x + 1) < 0 && !mark[x + 1]) --ret;
      }
      if (l) bit.add(l, l, cl);
      if (l < r - 1) bit.add(l + 1, r - 1, b);
      if (r < n) bit.add(r, r, -cr);
      for (auto &x: pt) {
        LL v = bit.get(x);
        if (x > 1 && v < 0 && bit.get(x - 1) > 0) ++ret;
        if (x + 1 < n && v > 0 && bit.get(x + 1) < 0 && !mark[x + 1]) ++ret;
        if (v == 0) eq.insert(x);
        if (v < 0) st.ins(1, 0, n, x, v);
      }
      for (auto &x: pt) mark[x] = false;
      printf("%d\n", ret);
    }
  }
} sol;

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) sol.run();
  return 0;
}

ZJP2016_I.cc

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
char s[MAXN][MAXN];

int main() {
  int T; scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) {
    int n, m; scanf("%d%d", &n, &m);
    memset(s, 0, sizeof(s));
    for (int i = 0; i < n; ++i) scanf("%s", s[i + 10] + 10);
    int ret = 0;
    for (int i = 0; i < n + 10; ++i) {
      for (int j = 0; j < m + 10; ++j) {
        ret += s[i][j + 1] == 'O' || s[i + 1][j] == '/' || s[i + 1][j + 1] == '|' ||
          s[i + 1][j + 2] == '\\' || s[i + 2][j] == '(' || s[i + 2][j + 2] == ')';
      }
    }
    cout << ret << endl;
  }
  return 0;
}

ZJP2016_J.cc

#include<bits/stdc++.h>

using namespace std;

struct Pt{
	double x, y, z;
} A,B,C,D;

const double eps = 1e-8;
const double _5 = sqrt(5.0);
const double _2 = sqrt(2.0);
double f[3];

typedef pair<Pt, Pt> PPP;

struct Pi{
	int x, y, z;
};

bool operator < (const Pi & a, const Pi & b){
	return (a.x < b.x);
}

bool operator == (const Pi & a, const Pi & b){
	return (a.x == b.x && a.y == b.y && a.z == b.z);
}

void Pit(const Pt & X){
	cout<<X.x<<' '<<X.y<<' '<<X.z<<endl;
}

bool operator == (const Pt & a, const Pt & b){
	return (fabs(a.x - b.x) < eps && fabs(a.y - b.y) < eps && fabs(a.z - b.z) < eps);
}

Pt work(Pt X, int k){
	return (Pt){X.x - 0.5 + (k & 1), X.y - 0.5 + ((k >> 1) & 1), X.z - 0.5 + ((k >> 2) & 1)};
}

/******************************/

#ifdef SPFA
	#define MAXD 60
#else
	#define MAXD 30
#endif

bool dis2_inRange(int x, int y, int z){
	return 0 <= x && x <= MAXD && 0 <= y && y <= MAXD && 0 <= z && z <= MAXD;
}

inline double dis2_getDis(int cnt){
	return cnt > 3 ? 1E100 : cnt == 3 ? _5 : cnt == 2 ? _2 : 1.0;
}

int dis2_getDis(int x, int y, int z, int ux, int uy, int uz){
	const int t = -2;
	if (((x | 1) != (ux | 1) || (y | 1) != (uy | 1) || (z | 1) != (uz | 1))
		&& ((x + (x & 1)) != (ux + (ux & 1)) || (y + (y & 1)) != (uy + (uy & 1)) || (z + (z & 1)) != (uz + (uz & 1))))
		return 4;
	return (x != ux) + (y != uy) + (z != uz);
}

void dis2_pre(Pi st, double (&dis)[MAXD + 1][MAXD + 1][MAXD + 1], int (&dt)[MAXD + 1][MAXD + 1][MAXD + 1][3]){
	static bool in[MAXD + 1][MAXD + 1][MAXD + 1];
	for (int i = 0; i <= MAXD; ++i)
		for (int j = 0; j <= MAXD; ++j)
			for (int k = 0; k <= MAXD; ++k){
				dis[i][j][k] = 1E100;
				in[i][j][k] = false;
				dt[i][j][k][0] = dt[i][j][k][1] = dt[i][j][k][2] = 0;
			}
	dis[st.x][st.y][st.z] = 0;
	queue<Pi> Q;
	Q.push(st);
	while (!Q.empty()){
		Pi u = Q.front();
		Q.pop();
//		fprintf(stderr, "start update: %d %d %d\n", u.x, u.y, u.z);
		for (int i = -1; i <= 1; ++i)
			for (int j = -1; j <= 1; ++j)
				for (int k = -1; k <= 1; ++k){
					int x = u.x + i, y = u.y + j, z = u.z + k;
					if (dis2_inRange(x, y, z)){
						int tmp = dis2_getDis(u.x, u.y, u.z, x, y, z);
						if (dis[x][y][z] > dis[u.x][u.y][u.z] + dis2_getDis(tmp)){
							dis[x][y][z] = dis[u.x][u.y][u.z] + dis2_getDis(tmp);
							dt[x][y][z][0] = dt[u.x][u.y][u.z][0];
							dt[x][y][z][1] = dt[u.x][u.y][u.z][1];
							dt[x][y][z][2] = dt[u.x][u.y][u.z][2];
							++dt[x][y][z][tmp - 1];
//							printf("%d %d %d\n", x, y, z);
							if (!in[x][y][z]){
//								puts("- =");
								in[x][y][z] = true;
								Q.push((Pi){x, y, z});
							}
						}
					}
				}
		in[u.x][u.y][u.z] = false;
	}
}

double dis2(Pi st, Pi ed){
	static bool used = false;
	static double dis[8][MAXD + 1][MAXD + 1][MAXD + 1];
	static int dt[8][MAXD + 1][MAXD + 1][MAXD + 1][3];

	/* prework */
	if (!used){
		used = true;
		for (int i = 0; i < 8; ++i)
			dis2_pre((Pi){i >> 2 & 1, i >> 1 & 1, i & 1}, dis[i], dt[i]);
	}

	int dx = ed.x - st.x, dy = ed.y - st.y, dz = ed.z - st.z;

	if (dx < dy){
		swap(dx, dy);
		swap(st.x, st.y);
		swap(ed.x, ed.y);
	}
	if (dx < dz){
		swap(dx, dz);
		swap(st.x, st.z);
		swap(ed.x, ed.z);
	}
	if (dy < dz){
		swap(dy, dz);
		swap(st.y, st.z);
		swap(ed.y, ed.z);
	}

	int cnt2 = 0, cnt1 = 0;
#ifndef SPFA
	int Maki = 5;
	int tx = max(0, dx - Maki) & -4, ty = max(0, dy - Maki) & -4, tz = max(0, dz - Maki) & -4;
//	printf("%d %d %d\n", tx, ty, tz);
	dx -= tx, dy -= ty, dz -= tz;
	if (ty + tz <= tx){
		tx -= cnt2 = ty + tz;
		cnt1 += max(0, tx - dy - dz);
		dx += min(dy + dz, tx);
	}
	else
		cnt2 += tx + ty + tz >> 1;
//	printf("- %d %d %d, %d %d\n", dx, dy, dz, cnt1, cnt2);
//	printf("st: %d %d %d\n", st.x, st.y, st.z);
#endif
	ed.x = st.x + dx;
	ed.y = st.y + dy;
	ed.z = st.z + dz;
	int type = st.x << 2 | st.y << 1 | st.z;
//	printf("%d %d %d\n", cnt1 + dt[type][ed.x][ed.y][ed.z][0], cnt2 + dt[type][ed.x][ed.y][ed.z][1], dt[type][ed.x][ed.y][ed.z][2]);
	return cnt1 + cnt2 * _2 + dis[type][ed.x][ed.y][ed.z];
}

#undef MAXD

/******************************/

double _dis2(Pt P, Pt Q){
	f[0] = fabs(P.x - Q.x);
	f[1] = fabs(P.y - Q.y);
	f[2] = fabs(P.z - Q.z);
	sort(f, f + 3);
	f[2] -= f[1];
	f[1] -= f[0];
	return _5 * f[0] + _2 * f[1] + f[2];
}

Pt operator -(const Pt & a, const Pt & b){
	return (Pt){a.x - b.x, a.y - b.y, a.z - b.z};
}

Pt operator +(const Pt & a, const Pt & b){
	return (Pt){a.x + b.x, a.y + b.y, a.z + b.z};
}

Pt operator *(const Pt & a, double x){
	return (Pt){a.x * x, a.y * x, a.z * x};
}

double sqr(double x){
	return x * x;
}

inline double len(const Pt & a){
	return sqrt(sqr(a.x)+sqr(a.y)+sqr(a.z));
}

double dg(double x, double y){
	return sqrt(sqr(x) + sqr(y));
}

PPP a[100];

int like(double p, double q, double r){
	if (fabs(p - q) < eps && fabs(q - r) < eps)
		return 1;
	else
		return 0;
}

double le[100][100];

double Get_s(Pt p, Pt q){
	for(int i = 0; i < 12; i++)
		for(int j = 0; j < 12; j++){
			if (like(a[i].first.x, a[j].first.x, 0) || like(a[i].first.x, a[j].first.x, 1))
				le[i][j] = len(a[i].first - a[j].first);
			else if (like(a[i].first.y, a[j].first.y, 0) || like(a[i].first.y, a[j].first.y, 1))
				le[i][j] = len(a[i].first - a[j].first);
			else if (like(a[i].first.z, a[j].first.z, 0) || like(a[i].first.z, a[j].first.z, 1))
				le[i][j] = len(a[i].first - a[j].first);
			else
				le[i][j] = 12345678;
		}
	for(int i = 0; i < 12; i++){
		if (like(a[i].first.x, p.x, 0) ||like(a[i].first.x, p.x, 1) ||
			like(a[i].first.y, p.y, 0) ||like(a[i].first.y, p.y, 1) ||
			like(a[i].first.z, p.z, 0) ||like(a[i].first.z, p.z, 1))
			le[i][13] = le[13][i] = len(p - a[i].first);
		else
			le[i][13] = le[13][i] = 12345678;
		if (like(a[i].first.x, q.x, 0) ||like(a[i].first.x, q.x, 1) ||
			like(a[i].first.y, q.y, 0) ||like(a[i].first.y, q.y, 1) ||
			like(a[i].first.z, q.z, 0) ||like(a[i].first.z, q.z, 1))
			le[i][12] = le[12][i] = len(q - a[i].first);
		else
			le[i][12] = le[12][i] = 12345678;
	}
	le[13][13] = le[12][12] = 0;
	if (like(p.x, q.x, 0) || like(p.y, q.y, 0) || like(p.z, q.z, 0) || like(p.x, q.x, 1) || like(p.y, q.y, 1) || like(p.z, q.z, 1))
		le[13][12] = le[12][13] = len(p - q);
	else
		le[13][12] = le[12][13] = 12345678;
	for(int k = 0; k < 14; k++)
		for(int i = 0; i < 14; i++)
			for(int j = 0; j < 14; j++)
				le[i][j] = min(le[i][j] , le[i][k] + le[k][j]);
	return le[12][13];
}

double tf(Pt p, Pt q){
	for(int i = 0; i <= 1; i++)
		for(int j = 0; j <= 1; j++)
			a[(i << 1) + j + 0] = (PPP){(Pt){i, j, rand()/(double)(RAND_MAX)}, (Pt){0, 0, 1}};
	for(int i = 0; i <= 1; i++)
		for(int j = 0; j <= 1; j++)
			a[(i << 1) + j + 4] = (PPP){(Pt){i, rand()/(double)(RAND_MAX), j}, (Pt){0, 1, 0}};
	for(int i = 0; i <= 1; i++)
		for(int j = 0; j <= 1; j++)
			a[(i << 1) + j + 8] = (PPP){(Pt){rand()/(double)(RAND_MAX), i, j}, (Pt){1, 0, 0}};
	double now = Get_s(p, q);
	double t = 0.5;
	while(t > 0.001){
		int flag = 0;
		for(int i = 0; i < 12; i++)
			if (!flag){
				a[20] = a[i];
				a[i].first = a[i].first + (a[i].second * t);
				double tmp = Get_s(p, q);
				if (tmp < now){
					flag = 1;
					while(tmp < now){
						now = tmp;
						a[20] = a[i];
						a[i].first = a[i].first + (a[i].second * t);
						tmp = Get_s(p, q);
					}
				}
				a[i] = a[20];
			}
		t *= 0.9;
	}
	return now;
}

double dis1(Pt P, Pt Q, Pt R){
//	puts("QAQ");
	P = P - R;
	Q = Q - R;
	P.x += 0.5, P.y += 0.5, P.z += 0.5;
	Q.x += 0.5, Q.y += 0.5, Q.z += 0.5;
//	Pit(P), Pit(Q);
	double ans = 10;
	for(int ts = 0; ts < 100; ts++){
//		puts("= -");
		ans = min(ans, tf(P, Q));
	}
//	cout<<"tf:\t"<<ans<<endl;
	return ans;
}

double _dis1(Pt P, Pt Q, Pt R){
//	puts("#############################");
/*	Pit(P);
	Pit(Q);
	Pit(R);
*/	P = P - R;
	Q = Q - R;
/*	Pit(P);
	Pit(Q);
*/	if (fabs(fabs(P.x) - 0.5) > eps){
		if (fabs(fabs(P.y) - 0.5) <= eps){
			swap(P.y, P.x);
			swap(Q.y, Q.x);
		}
		else{
			swap(P.z, P.x);
			swap(Q.z, Q.x);
		}
	}
	if (fabs(P.x + 0.5) < eps){
		P.x = -P.x, Q.x = -Q.x;
	}
	if (fabs(Q.x - 0.5) < eps){//On the same face
	//	cout<<"tl:\t"<<sqrt(sqr(P.y - Q.y) + sqr(P.z - Q.z))<<endl;
		return sqrt(sqr(P.y - Q.y) + sqr(P.z - Q.z));
	}
	if (fabs(fabs(Q.y) - 0.5) < eps || fabs(fabs(Q.z) - 0.5) < eps){//have a common edge
		if (fabs(fabs(Q.y) - 0.5) > eps){
			swap(Q.y, Q.z);
			swap(P.y, P.z);
		}
		if (fabs(Q.y + 0.5) < eps){
			Q.y = -Q.y, P.y = -P.y;
		}
	//	cout<<"tl:\t"<<min(dg(1-P.y-Q.x, P.z-Q.z), min(dg(1-P.y-Q.z, 1-P.z-Q.x), dg(1+P.z-Q.x,1+Q.z-P.y)))<<endl;
		return min(dg(1-P.y-Q.x, P.z-Q.z), min(dg(1-P.y-Q.z, 1-P.z-Q.x), dg(1+P.z-Q.x,1+Q.z-P.y)));
	}
	//On the opposite face
	double sum = 12345678;
	//passing another face
	sum = min(sum , dg(2 - P.z - Q.z, P.y - Q.y));
	sum = min(sum , dg(2 + P.z + Q.z, P.y - Q.y));
	sum = min(sum , dg(2 + P.y + Q.y, P.z - Q.z));
	sum = min(sum , dg(2 - P.y - Q.y, P.z - Q.z));
	//passing two other faces
	sum = min(sum, dg(2 - P.y - Q.z, 1 - P.z - Q.y));
	sum = min(sum, dg(2 - P.y + Q.z, 1 + P.z - Q.y));
	sum = min(sum, dg(2 + P.y - Q.z, 1 - P.z + Q.y));
	sum = min(sum, dg(2 + P.y + Q.z, 1 + P.z + Q.y));
	sum = min(sum, dg(2 + P.z + Q.y, 1 + P.y + Q.z));
	sum = min(sum, dg(2 + P.z - Q.y, 1 - P.y + Q.z));
	sum = min(sum, dg(2 - P.z + Q.y, 1 + P.y - Q.z));
	sum = min(sum, dg(2 - P.z - Q.y, 1 - P.y - Q.z));
//	cout<<"tl:\t"<<sum<<endl;
	return sum;
}

Pt getcenter(Pt X){
	int x, y, z;
	x = (int)(round(X.x));
	y = (int)(round(X.y));
	z = (int)(round(X.z));
	if (fabs(fabs(fmod(X.x, 1)) - 0.5) > eps){
		if ((y & 1) != (x & 1)){
			y = (int)(round(X.y * 2 - y));
		}
		if ((z & 1) != (x & 1)){
			z = (int)(round(X.z * 2 - z));
		}
	}
	else{
		if (fabs(fabs(fmod(X.y, 1)) - 0.5) > eps){
			if ((y & 1) != (x & 1)){
				x = (int)(round(X.x * 2 - x));
			}
			if ((z & 1) != (y & 1)){
				z = (int)(round(X.z * 2 - z));
			}
		}
		else{
			if ((z & 1) != (x & 1)){
				x = (int)(round(X.x * 2 - x));
			}
			if ((z & 1) != (y & 1)){
				y = (int)(round(X.y * 2 - y));
			}
		}
	}
	return (Pt){(double)x, (double)y, (double)z};
}

double Nico(Pt P, Pt Q){
	Pi p = (Pi){(int)(round(P.x + 0.5)), (int)(round(P.y + 0.5)), (int)(round(P.z + 0.5))};
	Pi q = (Pi){(int)(round(Q.x + 0.5)), (int)(round(Q.y + 0.5)), (int)(round(Q.z + 0.5))};
	q.x -= (p.x / 2) * 2, p.x -= (p.x / 2) * 2;
	if (p.x == -1){q.x += 2, p.x += 2;}
	q.y -= (p.y / 2) * 2, p.y -= (p.y / 2) * 2;
	if (p.y == -1){q.y += 2, p.y += 2;}
	q.z -= (p.z / 2) * 2, p.z -= (p.z / 2) * 2;
	if (p.z == -1){q.z += 2, p.z += 2;}
	if (q.x <= 0){
		q.x = 1 - q.x;
		p.x = 1 - p.x;
	}
	if (q.y <= 0){
		q.y = 1 - q.y;
		p.y = 1 - p.y;
	}
	if (q.z <= 0){
		q.z = 1 - q.z;
		p.z = 1 - p.z;
	}
	return dis2(p, q);
}

void ck(double x){
	assert(x >= -9999  && x <= 9999);
}

int main(){
//	freopen("J.in", "r", stdin);
//	freopen("J.out", "w", stdout);
//

	srand(time(NULL));
	int T;
	scanf("%d",&T);

/*
	for(int i = 0; i < 100;  i++){
		scanf("%lf%lf%lf", &A.x, &A.y, &A.z);
		scanf("%lf%lf%lf", &B.x, &B.y, &B.z);
		dis1(A, B, (Pt){0, 0, 0});
		_dis1(A, B, (Pt){0, 0, 0});
	}

	return 0;
*/
	while(T--){
		scanf("%lf%lf%lf", &A.x, &A.y, &A.z);
		scanf("%lf%lf%lf", &B.x, &B.y, &B.z);
		ck(A.x); ck(A.y); ck(A.z);
		ck(B.x); ck(B.y); ck(B.z);
		C = getcenter(A);
		assert((A.x - C.x - eps) <= 0.5 && (A.x - C.x + eps) >= -0.5);
		assert((A.y - C.y - eps) <= 0.5 && (A.y - C.y + eps) >= -0.5);
		assert((A.z - C.z - eps) <= 0.5 && (A.z - C.z + eps) >= -0.5);
		assert(((int)round(C.x - C.y)) % 2 == 0);
		assert(((int)round(C.x - C.z)) % 2 == 0);
		D = getcenter(B);
		assert((B.x - D.x - eps) <= 0.5 && (B.x - D.x + eps) >= -0.5);
		assert((B.y - D.y - eps) <= 0.5 && (B.y - D.y + eps) >= -0.5);
		assert((B.z - D.z - eps) <= 0.5 && (B.z - D.z + eps) >= -0.5);
		assert(((int)round(D.x - D.y)) % 2 == 0);
		assert(((int)round(D.x - D.z)) % 2 == 0);
		double ans = 1234567;
		if (C == D){
			ans = _dis1(A, B, C);
		}
		else{
			
			for(int i = 0; i < 8; i++)
				for(int j = 0; j < 8; j++){
				//	ans = min(ans,dis2(work(C, i), work(D, j)));
				//	dis1(A, work(C, i), C);
				//	_dis1(A, work(C, i), C);
				//	dis1(B, work(D, j), D);
				//	_dis1(B, work(D, j), D);
					ans = min(ans, _dis1(A, work(C, i), C) + _dis1(B, work(D, j), D) + Nico(work(C, i), work(D, j)));
				//	ans = min(ans, dis1(A, work(C, i), C) + dis1(B, work(D, j), D) + dis2(work(C, i), work(D, j)));
				}
		}
		printf("%.16f\n", ans);
	}
	return 0;
}
 

/*
0.733017 0.493771 1
0.429134 0 0.88777
tf:	0.678462
tl:	0.677924

0.25458 0 1
0.165501 1 0.459615
tf:	1.4132
tl:	1.4108

0.561626 0 0
1 0.0775424 0.207269
tf:	0.556202
tl:	0.555994

0 0.98381 1
1 0.962809 0.831134
tf:	1.06045
tl:	1.05357
*/

ZJP2016_K.cc

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 100000 + 10;
vector<PII> G[MAXN];
int X[MAXN], Y[MAXN], D[MAXN], C[MAXN];
LL ds[MAXN], ms[MAXN];
int n, m;

void run() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    G[i].clear();
    ms[i] = ds[i] = 1ll << 60;
  }
  for (int i = 0; i < m; ++i) {
    cin >> X[i] >> Y[i] >> D[i] >> C[i];
    G[X[i]].push_back(PII(Y[i], i));
    G[Y[i]].push_back(PII(X[i], i));
  }
  ds[0] = ms[0] = 0;
  queue<int> Q; Q.push(0);
  vector<bool> vs(n);
  while (!Q.empty()) {
    int u = Q.front(); Q.pop(); vs[u] = 0;
    for (auto &x: G[u]) {
      int v = x.first, w = D[x.second];
      if (ds[v] > ds[u] + w) {
        ds[v] = ds[u] + w;
        if (!vs[v]) vs[v] = 1, Q.push(v);
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    if (ds[X[i]] + D[i] == ds[Y[i]]) {
      ms[Y[i]] = min(ms[Y[i]], (LL)C[i]);
    }
    if (ds[Y[i]] + D[i] == ds[X[i]]) {
      ms[X[i]] = min(ms[X[i]], (LL)C[i]);
    }
  }
  LL SD = 0, SC = 0;
  for (int i = 0; i < n; ++i) SD += ds[i], SC += ms[i];
  cout << SD << " " << SC << endl;
}

int main() {
  int T; cin >> T;
  for (int cas = 1; cas <= T; ++cas) run();
  return 0;
}

ZJP2016_L.cc

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T; cin >> T;
  for (int cas = 1; cas <= T; ++cas) {
    int n; cin >> n;
    for (int i = n; i >= 1; --i) {
      int x; cin >> x; n += x;
    }
    cout << n << endl;
  }
  return 0;
}