10th Japan Olympiad in Informatics final round

t1.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
  int m,n,k; scanf("%d%d%d", &m, &n, &k);
  static int cnt[3][1010][1010];
  // int (*cnt)[1010][1010] = new int[3][1010][1010];
  for(int i = 0; i < 3; i++) {
    for(int y = 0; y <= m; y++) cnt[i][y][0] = 0;
    for(int x = 0; x <= n; x++) cnt[i][0][x] = 0;
  }
  for(int y = 0; y < m; y++) {
    static char line[1010]; scanf(" %[JOI]", line);
    for(int x = 0; x < n; x++) {
      for(int i = 0; i < 3; i++) {
	int curr = ("JOI"[i] == line[x]) ? 1 : 0;
	cnt[i][y+1][x+1] = cnt[i][y][x+1] + cnt[i][y+1][x] - cnt[i][y][x] + curr;
      }
    }
  }
  for(int j = 0; j < k; j++) {
    int a,b,c,d; scanf("%d%d%d%d", &a, &b, &c, &d); a--; b--;
    for(int i = 0; i < 3; i++) {
      printf("%d%c", cnt[i][a][b] - cnt[i][a][d] - cnt[i][c][b] + cnt[i][c][d], "  \n"[i]);
    }
  }
  return 0;
}

t2.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int n,k; scanf("%d%d", &n, &k);
  static long long books[10][2001];
  int books_len[10];
  fill(books_len, books_len+10, 0);
  for(int i = 0; i < n; i++) {
    int c,g; scanf("%d%d", &c, &g); g--;
    books[g][books_len[g]++] = c;
  }
#if 0
  k = 2000;
  for(int i = 0; i < 10; i++) {
    books_len[i] = 2000;
    for(int j = 0; j < 2000; j++) {
      books[i][j] = 1;
    }
  }
#endif
  for(int i = 0; i < 10; i++) {
    sort(books[i], books[i]+books_len[i], greater<int>());
    for(int j = 0; j < books_len[i]; j++) books[i][j]+=j*2;
    long long subsum = 0;
    for(int j = 0; j < books_len[i]; j++) {
      long long t = subsum;
      subsum += books[i][j];
      books[i][j] = t;
    }
    books[i][books_len[i]] = subsum;
    /*
    printf("%d: ", i);
    for(int j = 0; j <= books_len[i]; j++) {
      printf("%lld, ", books[i][j]);
    }
    printf("\n");
    */
  }
  static long long dp[11][2001];
  fill(dp[0], dp[0]+k+1, -1);
  dp[0][0] = 0;
  for(int i = 0; i < 10; i++) {
    fill(dp[i+1], dp[i+1]+k+1, -1);
    for(int j = 0; j <= books_len[i]; j++) {
      for(int j2 = 0; j+j2 <= k; j2++) {
	if(dp[i][j2] == -1) continue;
	dp[i+1][j+j2] = max(dp[i+1][j+j2], dp[i][j2]+books[i][j]);
      }
    }
  }
  /*
  for(int i = 0; i <= 10; i++) {
    printf("%d: ", i);
    for(int j = 0; j <= k; j++) {
      printf("%lld ", dp[i][j]);
    }
    printf("\n");
  }
  */
  printf("%lld\n", dp[10][k]);
  return 0;
}

t3.cpp

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Edge {
  int a,b,l;
};

struct Arc {
  int f,t,l;
  Arc *next;
};

int main() {
  int n,m,k; scanf("%d%d%d", &n, &m, &k);
  static Edge edges[100000];
  static Arc arcs[200000];
  static Arc *varc[3000];
  fill(varc, varc+n, (Arc*)NULL);
  for(int i = 0; i < m; i++) {
    int a,b,l; scanf("%d%d%d", &a, &b, &l); a--; b--;
    edges[i].a = a;
    edges[i].b = b;
    edges[i].l = l;
    arcs[i*2+0].f = a;
    arcs[i*2+0].t = b;
    arcs[i*2+0].l = l;
    arcs[i*2+0].next = varc[a];
    varc[a] = &arcs[i*2+0];
    arcs[i*2+1].f = b;
    arcs[i*2+1].t = a;
    arcs[i*2+1].l = l;
    arcs[i*2+1].next = varc[b];
    varc[b] = &arcs[i*2+1];
  }
  priority_queue<pair<int,int> > pq;
  int tim[3000];
  fill(tim, tim+n, -1);
  for(int i = 0; i < k; i++) {
    int s; scanf("%d", &s); s--;
    pq.push(make_pair(0,s));
  }
  while(!pq.empty()) {
    int t = pq.top().first;
    int x = pq.top().second;
    pq.pop();
    if(tim[x]>=0) continue;
    tim[x] = -t;
    for(Arc *arc = varc[x]; arc; arc=arc->next) {
      if(tim[arc->t]==-1) {
	pq.push(make_pair(t-arc->l,arc->t));
      }
    }
  }
  int max_cnt = 0;
  for(int i = 0; i < m; i++) {
    int a = edges[i].a;
    int b = edges[i].b;
    int l = edges[i].l;
    max_cnt = max(max_cnt, tim[a] + tim[b] + l);
  }
  printf("%d\n", (max_cnt+1)/2);
  return 0;
}

t4.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

int main() {
  int w,h,n; scanf("%d%d%d", &w, &h, &n);
  static pair<long long,int> xs[100000];
  static pair<long long,int> ys[100000];
  static int xid[100000];
  static int yid[100000];
  for(int i = 0; i < n; i++) {
    int x,y; scanf("%d%d", &x, &y);
    xs[i] = make_pair(x,i);
    ys[i] = make_pair(y,i);
  }
  sort(xs, xs+n);
  sort(ys, ys+n);
  for(int i = 0; i < n; i++) {
    xid[xs[i].second] = i;
    yid[ys[i].second] = i;
  }
  static long long xcc[100000];
  static long long ycc[100000];
  fill(xcc, xcc+n, 0);
  fill(ycc, ycc+n, 0);
  long long subsum;
  subsum = 0; for(int i = 1; i < n; i++) xcc[i] += (subsum += i*(xs[i].first-xs[i-1].first));
  subsum = 0; for(int i = 1; i < n; i++) ycc[i] += (subsum += i*(ys[i].first-ys[i-1].first));
  subsum = 0; for(int i = n-1; i > 0; i--) xcc[i-1] += (subsum += (n-i)*(xs[i].first-xs[i-1].first));
  subsum = 0; for(int i = n-1; i > 0; i--) ycc[i-1] += (subsum += (n-i)*(ys[i].first-ys[i-1].first));
  pair<long long,pair<long long,long long> > minval = make_pair(INT_MAX,make_pair(-1,-1));
  for(int i = 0; i < n; i++) {
    int selx,sely;
    if(n&1) selx = n/2;
    else if(xid[i] < n/2) selx = n/2;
    else selx = n/2-1;
    if(n&1) sely = n/2;
    else if(yid[i] < n/2) sely = n/2;
    else sely = n/2-1;
    long long cnt = (xcc[selx]+ycc[sely])*2 - abs(xs[xid[i]].first-xs[selx].first) - abs(ys[yid[i]].first-ys[sely].first);
    pair<long long,pair<long long,long long> > val = make_pair(cnt, make_pair(xs[selx].first,ys[sely].first));
    minval = min(minval, val);
  }
  printf("%lld\n%lld %lld\n",minval.first,minval.second.first,minval.second.second);
  return 0;
}

t5.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int main() {
  int n; scanf("%d", &n);
  static pair<int,int> bacs[300000];
  for(int i = 0; i < n; i++) {
    int a,b;
    scanf("%d%d", &a, &b);
    bacs[i] = make_pair(-b,a);
  }
#if 0
  n = 300000;
  for(int i = 0; i < n; i++) {
    bacs[i] = make_pair(-100000,1);
  }
#endif
  sort(bacs, bacs+n);
  int lo=0,hi=n+1;
  while(hi-lo>1) {
    int k = (lo+hi)>>1;
    priority_queue<int> ais;
    long long aisum = 0;
    bool succeeded = false;
    for(int i = 0; i < n; i++) {
      int bi = -bacs[i].first;
      int ai = bacs[i].second;
      aisum += ai;
      ais.push(ai);
      while(aisum > (long long)k*bi) {
	aisum -= ais.top();
	ais.pop();
      }
      if((int)ais.size() >= k) succeeded = true;
    }
    if(succeeded) lo=k; else hi=k;
  }
  printf("%d\n", lo);
  return 0;
}