Codeforces Round #638 (Div. 2) E Phoenix and Berries

首先考虑只按颜色分配的当前答案ans，那么最后剩下的果子数在[0,2k-2]之间，如果剩下的果子数在[0,k-1]之间，那么当前的ans就是最终答案，如果剩下的果子数在[k,2k-2]之间，那么最多答案还可以加一，也就是答案有可能是ans+1，下面我们用dp判断有无这种可能性

举个例子：

n=1 k=5

a1=4 b1=3

那么可以放弃一对(5,5)，而选择(4,1)、(3,2)或(2,3)，最后再用剩下的（这次剩下的和之前剩下的）填上这个(5,5)，那么答案就增加了1

但是直接这样写时间复杂度太高了，和a[i]、b[i]相关

可以考虑每次填上一对(5,5)时直接把它拿出来，也就是对k取模即可

时空复杂度都是O(n^3)

（写到这里已经可以过这道题了，下面考虑进一步优化：）

空间上可以考虑i+j==k，滚动数组分别优化掉一维，空间复杂度O(n)

时间上可以考虑bitset优化，时间复杂度O(n^3/32)

下面的代码是无优化的：

（一个想法：可能可以用网络流实现，大噶有会的可以在评论里回复我或者Q我，谢谢大噶~）

#include

using namespace std;

#define LL long long

bool f[505][505][505];
int n, i, g[505][505], j, t;
LL suma, sumb, ans, p, k, a[505], b[505], ta, tb;

int main (void)
{
	scanf("%d%lld",&n,&k);
	for (i=1; i<=n; i++) {
	    scanf("%lld%lld",&a[i],&b[i]);
	    suma+=a[i];
	    sumb+=b[i];
	}
	ans=suma/k+sumb/k;
	suma%=k,sumb%=k;
	if (suma+sumb