2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest J. JPEG is Awesome!

問題

K日間にわたって写真を撮る。カメラの記憶容量はLであり、写真一枚が消費する記憶容量は非圧縮の場合Dである。

i日目にはti枚の写真を撮り、j番目の写真のできばえはQijである。
写真は好きなものを好きなだけ削除することができる。
また、同じ日の写真は同じ圧縮率α（0≦α≦1）で圧縮することができる。
圧縮した場合、記憶容量はα倍、できばえはα倍になる。
同じ日の写真を、違う圧縮率で圧縮することはできない。

できばえの合計値の最大値を求めよ。
出力は分数の形で出力せよ。

制約条件

K≦10^6
L, D≦10^9
写真の合計枚数≦10^9

方針

0. 同じ日の中で写真はできばえの良い順に使うとしてよい。
1. 圧縮する日は高々一日だけでよい。
2. 非圧縮の場合の容量の和はL + D未満であるとしてよい

1. 最適解において圧縮した日が二日あるなら、1容量あたりのできばえが多い日のαを大きくすれば得をするのでこれは最大性に反する。
2. 最適解において、L + D以上なら、圧縮している日の最後の一枚を削ればできばえが増加する。

なので、i日目を圧縮すると仮定し、i日目にj枚使うとするのを全通り試せばよい。
2.より採用する写真の枚数(m)はあらかじめわかっているので、
i日目にj枚使うとすると、i日以外では貪欲にいい順にm - j枚とればよい。

これは適切なデータ構造（BITなど）を使えばO(log(n))時間でできる。
分数のところは多倍長とか使って頑張る。

ソースコード

const int MX = 1000010;
ll bit[MX], bit2[MX];
inline void add(ll *bit, int i, ll x){
	for(i++ ; i < MX; i += i & -i) bit[i] += x;
}
inline ll sum(ll *bit, int i){
	ll res = 0;
	for(i++; i; i -= i & -i) res += bit[i];
	return res;
}
inline int get(ll *bit, int k){
	if(k == 0) return -1;
	if(sum(bit, MX - 2) < k) return -inf;
	
	int lo = 0, hi = 1 << 32 - __builtin_clz(MX), mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(mid > MX || bit[mid] >= k) hi = mid;
		else k -= bit[lo = mid];
	}
	return lo;
}

ll sums[MX];
int K, L, D, delta;
vector<vi> v, pos;

inline void calc(ll o, ll cursum, int j, ll &d, ll &x, ll &y){
	d = o;
	x = cursum;
	y = (j + 1ll) * D;
	ll g = __gcd(x, y), z = ((j + 1ll) * D - delta);
	x /= g; y /= g;
	g = __gcd(z, y);
	z /= g; y /= g;
	
	if(x * 1.0 * z <= 1e18){
		x *= z;
		d += x / y; x %= y;
	}
	else{
		BigNum a = convert(x), c = convert(z);
		pair<BigNum, Int> m = divmod(a * c, y);
		stringstream ss;
		ss << m.first;
		d += atoll(ss.str().c_str());
		x = m.second;
	}
}

int main(){
	scanf("%d%d%d", &K, &L, &D);
	v.resize(K);
	pos.resize(K);
	
	vector<pi> in;
	
	rep(i, K){
		int t, u; scanf("%d", &t);
		rep(j, t) scanf("%d", &u), v[i].pb(-u);
		sort(all(v[i]));
	}
	random_shuffle(all(v));
	rep(i, K){
		rep(j, v[i].size()) in.pb(mp(v[i][j], i));
	}
	sort(all(in));
	int n = in.size();
	
	rep(i, n){
		pos[in[i].second].pb(i);
		sums[i + 1] = sums[i] - in[i].first;
		
		add(bit, i, 1);
	}
	
	ll ans = sums[min(n, L / D)];
	int usecnt = (L + D - 1) / D;
	delta = (ll)usecnt * D - L;
	long double ansd = ans;
	ll d = ans, x = 0, y = 1;
	
	
	#if 0
	rep(i, n) cerr<<-in[i].first<<(i==n-1?"\n":" ");
	rep(i, n) cerr<<in[i].second<<(i==n-1?"\n":" ");
	rep(i, K) rep(j, pos[i].size()) cerr<<pos[i][j]<<(j==pos[i].size()-1?"\n":" ");
	
	dbg(usecnt);
	dbg(delta);
	dbg(ansd);
	#endif
	
	if(usecnt > n){
		cout << ans << endl;
		return 0;
	}
	assert(usecnt <= n);
	assert(delta < D);
	assert(n <= 1000000);
	
	vi ord;
	rep(i, K) ord.pb(i);
	random_shuffle(all(ord));
	
	rep(ii, K){
		int i = ord[ii];
		vi &u = v[i];
		int t = u.size();
		ll cursum = 0;
		
		assert(sum(bit2, MX - 3) == 0);
		assert(sum(bit, MX - 3) == n);
		
		rep(j, t){
			add(bit2, pos[i][j], -u[j]);
			add(bit, pos[i][j], -1);
		}
		rep(j, t){
			if(j >= usecnt) break;
			
			int p = get(bit, usecnt - j - 1);
			cursum -= u[j];
			
			//dbg(j); dbg(p);
			
			if(p == -inf) continue;
			/*
			dbg(n - t + j + 1);
			dbg(usecnt);
			*/
			assert(n - t + j + 1 >= usecnt);
			
			ll o = sums[p + 1] - sum(bit2, p);
			long double tmp = o + 1.0l * cursum * ((j + 1ll) * D - delta) / (j + 1) / D;
			
			assert(o <= ans);
			if(ansd >= tmp + EPS) continue;
			
			ll dd, xx, yy;
			calc(o, cursum, j, dd, xx, yy);
			
			if(d < dd || d == dd &&
				convert(x) * yy < convert(xx) * y){
			
				ansd = tmp;
				d = dd;
				x = xx;
				y = yy;
			}
			assert(x < y);
			assert(__gcd(x, y) == 1);
		}
		rep(j, t){
			add(bit2, pos[i][j], u[j]);
			add(bit, pos[i][j], 1);
		}
	}
	cout << d;
	if(x) cout << " + " << x << "/" << y;
	cout << endl;
	dbg((double)ansd);
	
	return 0;
}