Wc2020 course selection

Title Description

LOJ3331

Topic analysis

Consider the restricted and unrestricted categories separately .

Make $X=T-\sum s_i$

Unrestricted classification , Find out $f[i][j],j\in [s_i,s_i+X+2]$, It means the first one $i$ Get at least $j$ The minimum mental effort required for credits , Greater than $s_i+X+2$ There's no use in that part of , Because you can learn one less course to make the answer better .

Then merge them , Find out $f^{\prime }[j],j\in [s^{\prime },s^{\prime }+X+2]$,$s^{\prime }$ The meaning is $\sum s_i$.
The merger is $O(X^2)$ Of , The complexity of this part $O(m{X}^2)$

Consider how to ask for $f[i][j]$

If the credits are only 1,2,$j$ If it is an odd number, the least expensive 1, Convert to even .$j$ If it is an even number, put 1 Two by two 2, Before you take it again $\frac{j}{2}$ Small .

So just enumerate 3 How many did you choose . Preprocessing ( Sort + Merger ) $O(N\log N)$, enumeration $O(XN)$

Restricted classification , Find out for courses that do not involve restrictions $f[i][j],j\in [s_i-{\sum }_{k\in P}{w}_k,s_i+X+2]$, That is, set aside some points for those courses that involve restrictions .

then $2^p$ Enumerations limit how courses are selected , Use the credits obtained to update the $f[i][j]$, Then with $f^{\prime }$ Merge , Need merger $p$ Time , Complexity $O(2^{p}p(p+X^2))$, The merged results are $f[T]$ Plus the mental value that limits the contribution of the relationship .

（ I think the train of thought is quite NOIP Of , It's not too hard to write ）
Code：

#include<bits/stdc++.h>
#define maxn 500005
#define maxm 50005
using namespace std;
char cb[1<<20],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)
void read(int &a){
    
	char c;while(!isdigit(c=getc()));
	for(a=c-'0';isdigit(c=getc());a=a*10+c-'0');
}
const int inf = 0x3f3f3f3f;
int m,N,T,P,X,n[maxm],s[maxm],w[maxn],c[maxn],L[maxm],R[maxm],bel[maxn],banval[maxm];
int ans=inf;
int p[maxn],num,loc[15],extra[maxm],blk[15];
bool ban[maxn];
struct limit{
    
	int op,a1,a2,b1,b2,c;
}q[12*12];
int A[4][maxn],B[4],S1[maxn*3+50],S2[maxn*3+50];
struct node{
    
	int a[85];
	node(){
    memset(a,0x3f,sizeof a);}
	void init(int l,int r){
    
		for(int i=1;i<=3;i++) sort(A[i]+1,A[i]+1+B[i]);
		for(int i=1;i<=r;i++) S1[i]=S2[i]=inf;
		A[1][B[1]+1]=inf,A[2][B[2]+1]=inf;
		for(int i=1,j=1,k=0;i<B[1]||j<=B[2];k++)
			if(A[1][i]+A[1][i+1]<=A[2][j]) S1[k+1]=S1[k]+A[1][i]+A[1][i+1],i+=2;
			else S1[k+1]=S1[k]+A[2][j],j++;
		for(int i=2,j=1,k=0;i<B[1]||j<=B[2];k++)
			if(A[1][i]+A[1][i+1]<=A[2][j]) S2[k+1]=S2[k]+A[1][i]+A[1][i+1],i+=2;
			else S2[k+1]=S2[k]+A[2][j],j++;
		if(!B[1]) A[1][1]=inf;
		for(int i=r;i>=l;i--){
    
			int ret=inf;
			for(int j=0,br=0;j<=B[3]&&j*3<=i;j++,br+=A[3][j])
				ret=min(ret,br+((i-j*3)&1?A[1][1]+S2[(i-j*3)/2]:S1[(i-j*3)/2]));
			a[i-l]=min(ret,a[i+1-l]);
		}
	}
	node operator + (const node &g)const{
    
		node h;
		for(int i=0;i<=X+2;i++) for(int j=0;j<=i;j++) h.a[i]=min(h.a[i],a[j]+g.a[i-j]);
		return h;
	}
	node upd(int l,int score){
    
		node g;
		for(int i=0;i<=X+2;i++) g.a[i]=a[l+i-score];
		return g;
	}
}f[maxm],F,G;
int main()
{
    
	freopen("courses.in","r",stdin);
	//freopen("courses.out","w",stdout);
	read(m),read(T); int Sum=0;
	for(int i=1;i<=m;i++){
    
		read(n[i]),read(s[i]),N+=n[i],X+=s[i];
		L[i]=R[i-1]+1,R[i]=L[i]+n[i]-1; int sum=0;
		for(int j=L[i];j<=R[i];j++) read(w[j]),read(c[j]),bel[j]=i,sum+=w[j];
		if(sum<s[i]) return puts("-1"),0;
		Sum+=sum;
	}
	if(Sum<T) return puts("-1"),0;
	X=max(0,T-X);
	read(P);
	for(int i=0;i<P;i++){
    
		read(q[i].op),read(q[i].a1),read(q[i].a2),read(q[i].b1),read(q[i].b2);
		if(q[i].op!=3) read(q[i].c);
		q[i].a2+=L[q[i].a1]-1,q[i].b2+=L[q[i].b1]-1;
		ban[q[i].a2]=ban[q[i].b2]=1;
		banval[q[i].a1]+=w[q[i].a2],banval[q[i].b1]+=w[q[i].b2];
	}
	F.a[0]=0;
	for(int i=1;i<=m;i++){
    
		B[1]=B[2]=B[3]=0;
		for(int j=L[i];j<=R[i];j++) if(!ban[j]) A[w[j]][++B[w[j]]]=c[j];
		f[i].init(s[i]-banval[i],s[i]+X+2);
		if(!banval[i]) F=F+f[i];
		else blk[++*blk]=i;
	}
	for(int i=1;i<=N;i++) if(ban[i]) loc[num]=i,p[i]=num++;
	for(int S=0;S<1<<num;S++){
    
		int ret=0;
		for(int i=0;i<P;i++){
    
			int x=p[q[i].a2],y=p[q[i].b2];
			if(S>>x&1 && S>>y&1){
    
				if(q[i].op==1) ret-=q[i].c;
				else if(q[i].op==2) ret+=q[i].c;
				else {
    ret=inf;break;}
			}
		}
		if(ret>=inf) continue;
		for(int i=1;i<=*blk;i++) extra[blk[i]]=0;
		for(int i=0;i<num;i++) if(S>>i&1) extra[bel[loc[i]]]+=w[loc[i]],ret+=c[loc[i]];
		G=F;
		for(int i=1;i<=*blk;i++) G=G+f[blk[i]].upd(banval[blk[i]],extra[blk[i]]);
		if(G.a[X]<inf) ans=min(ans,G.a[X]+ret);
	}
	printf("%d\n",ans<inf?ans:-1);
}