1348E - Phoenix and Berries - CodeForces Solution

#include<iostream>

#include<cstdio>

typedef long long ll;

template <typename T> T Max(T x, T y) { return x > y ? x : y; }

template <typename T> T Min(T x, T y) { return x < y ? x : y; }

template <typename T>

T &read(T &r) {

	r = 0; bool w = 0; char ch = getchar();

	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();

	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();

	return r = w ? -r : r;

}

int Mod(int x, int y) { return x < 0 ? (x + y) : (x >= y ? (x - y) : x); }

const int N = 510;

int n, k;

int a[N], b[N];

ll sa, sb, ans, f[N], g[N];

int Sum(int l, int r) {

	if(l <= r) return g[r] - (l == 0 ? 0 : g[l-1]);

	return g[r] + g[k-1] - g[l-1];

}

signed main() {

	read(n); read(k);

	for(int i = 1; i <= n; ++i) read(a[i]), read(b[i]), sa += a[i], sb += b[i];

	ans = sa / k + sb / k; sa %= k, sb %= k;

	if(sa + sb < k) {

		printf("%lld\n", ans);

		return 0;

	}

	f[0] = 1;

	for(int i = 1; i <= n; ++i) {

		for(int j = 0; j < k; ++j) g[j] = f[j];

		for(int j = 1; j < k; ++j) g[j] += g[j-1];

		for(int j = 0; j < k; ++j) 

			if(!f[j]) {

				int L = j-Min(a[i], k-1), R = j-Max(0, k-b[i]);

				if(L > R) continue ;

				L = Mod(L, k); R = Mod(R, k);

				if(Sum(L, R)) f[j] = 1;

			}

		for(int j = k - sb; j <= sa; ++j)

			if(f[j]) {

				printf("%lld\n", ans+1);

				return 0;

			}

	}

	printf("%lld\n", ans);

	return 0;

}