Problem: Example

Input

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1


Output

5

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#define  fr(i,x,y) for(i=x;i<=y;i++)
#define  frd(i,x,y) for(i=x;i>=y;i--)
const int maxn=310;
const int maxm=(int)2e5+10;
int n,m,T,p;
int have[maxn],a[maxn],left[maxn];
int want[maxn][maxn],ori[maxn][maxn];
int list[maxm][2];
int fa[maxn],sta[maxn];
void Read()
{	
	int i,j;
	scanf("%d%d%d",&n,&m,&T);
	fr(j,1,m)scanf("%d",&have[j]);
	memset(left+1,0,n*sizeof(int));
	fr(i,1,n)
	fr(j,1,m)
	{
		scanf("%d",&want[i][j]),ori[i][j]=want[i][j];
		if(want[i][j])left[i]++;
	}
	fr(i,1,T)scanf("%d%d",&list[i][0],&list[i][1]);
}
void Go_up(int low,int high)
{
	int i,j,p,r;
	fr(i,low+1,high)
	{
		p=list[i][0],r=list[i][1];
		have[r]--;
		want[p][r]--;
		if(!want[p][r])
		{
			left[p]--;
			if(!left[p])fr(j,1,m)have[j]+=ori[p][j];
		}
	}
}
void Go_down(int high,int low)
{
	int i,j,p,r;
	frd(i,high,low+1)
	{
		p=list[i][0],r=list[i][1];
		have[r]++;
		if(!want[p][r])
		{
			if(left[p]==0)fr(j,1,m)have[j]-=ori[p][j];
			left[p]++;
		}
		want[p][r]++;
	}
}
int Get_fa(int x)
{
	while(fa[x]!=x)sta[++sta[0]]=x,x=fa[x];
	while(sta[0])fa[sta[sta[0]--]]=x;
	return x;
}
bool Check()
{
	int i,j,cnt;
	bool bo;
	fr(i,1,n+1)fa[i]=i;
	memcpy(a+1,have+1,m*sizeof(int));
	cnt=0;
	bo=true;
	while(bo)
	{
		bo=false;
		for(i=Get_fa(1);i<=n;i=Get_fa(i+1))
		{
			fr(j,1,m)if(want[i][j]>a[j])break;
			if(j<=m)continue;
			cnt++;
			if(left[i]!=0)
				fr(j,1,m)a[j]+=ori[i][j]-want[i][j];
			bo=true;
			fa[i]=Get_fa(i+1);
			break;
		}
	}
	return cnt==n;
}
void Solve()
{
	int le,ri,mi;
	le=0,ri=T;
	p=0;
	while(le<=ri)
	{
		mi=(le+ri)>>1;
		if(mi>p)Go_up(p,mi);
		else Go_down(p,mi);
		p=mi;
		if(Check())le=mi+1;
		else ri=mi-1;
	}
	if(le>T)le=-1;
	printf("%d\n",le);
}
int main()
{
	Read();
	Solve();
}