Skip to content

Instantly share code, notes, and snippets.

@qnighy

qnighy/t1.cpp

Created Feb 14, 2011
Embed
What would you like to do?
10th Japan Olympiad in Informatics final round
#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;
}
#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;
}
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.