{{ message }}

Instantly share code, notes, and snippets.

# qnighy/t1.cpp

Created Feb 14, 2011
10th Japan Olympiad in Informatics final round
 #include #include #include 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; }
 #include #include #include #include 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()); 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; }
 #include #include #include #include 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 > 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; }
 #include #include #include #include using namespace std; int main() { int w,h,n; scanf("%d%d%d", &w, &h, &n); static pair xs[100000]; static pair 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 > 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 > 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; }
 #include #include #include #include using namespace std; int main() { int n; scanf("%d", &n); static pair 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 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; }