列队

题目描述

Sylvia 是一个热爱学习的女孩子。

代码

#include <bits/stdc++.h>
using namespace std;
int love[4010][4010],stall[4010],used[4010];
int n,m,k,p,ans;
bool find(int x){
for (int i=1;i<=m;i++){
if (love[x][i]==true&&used[i]==false){
used[i]=true;
if (stall[i]==0||find(stall[i])){
stall[i]=x;
return true;
}
}
}
return false;
}
int main() {
freopen("phalanx.in","r",stdin);
freopen("phalanx.out","w",stdout);
scanf("%d%d",&m,&n);
for (int i=1,a,b;i<=n;i++){
scanf("%d%d",&a,&b);
love[a][b]=1;
}
for (int i=1;i<=n;i++){
memset(used,0,sizeof(used));
find(i);
}
for (int i=1;i<=m;i++)
if (stall[i]>0) ans++;
printf("%d",m*(2*m-ans));
return 0;
}


小凯学数学

代码

#include <bits/stdc++.h>
#define pb push_back
#define inf INT_MAX
#define sc second
#define ft first
#define pii pair<int,int>
#define mid ((l+r)>>1)
#define mn(a,b) (a<b?a:b)
#define mx(a,b) (a>b?a:b)
#define maxn 50010
#define maxm 250
using namespace std;
int n,m,D[maxn],T[maxn],SD[maxn];
int cnt,L[maxn],R[maxn],belong[maxn];
void prepare(){
int len=sqrt(n);
L[1]=belong[1]=cnt=1;
for (int u=1;u<=n;u++){
belong[u]=cnt;
if (u%len) continue;
R[cnt]=u;
cnt++;
L[cnt]=u+1;
}
cnt=belong[n],R[cnt]=n;
}
int F[maxm][maxm][maxm],tcnt;
pii TM[maxn];
vector<pii> Vec[maxm],Pre[maxm],Suf[maxm];
int sta[maxn];
int S(int x,int y){return F[belong[x]][x-L[belong[x]]][y-L[belong[y]]];}
int G(int x,int y){return SD[y]-SD[x-1];}
void calc(vector<pii> &cur){
sort(TM+1,TM+1+tcnt);
int top=0;
for (int i=1;i<=tcnt;++i){
while(top&&TM[i].sc>=TM[sta[top]].sc) top--;
sta[++top]=i;
}
for (int i=1;i<=top;++i)
cur.pb(TM[sta[i]]);
}
void update(int x){
for (int i=L[x];i<=R[x];++i){
int tem=1<<30;
for (int j=i;j<=R[x];++j)
tem=mn(tem+D[j],T[j]),F[x][i-L[x]][j-L[x]]=tem;
}
tcnt=0;
for (int i=L[x];i<=R[x];++i)
for (int j=i;j<=R[x];++j)
TM[++tcnt]=pii(S(i,j),G(i,j));
calc(Vec[x]);
tcnt=0;
for (int i=L[x];i<=R[x];++i)
TM[++tcnt]=pii(S(L[x],i),G(L[x],i));
calc(Pre[x]);
tcnt=0;
for (int i=L[x];i<=R[x];++i)
TM[++tcnt]=pii(S(i,R[x]),G(i,R[x]));
calc(Suf[x]);
}
void init(){
for (int i=1;i<=cnt;i++)
update(i);
}
int find(vector<pii> cur,int tag){
int l=0,r=cur.size()-1,res;
while(l+1<r){
if (cur[mid].ft>cur[mid].sc+tag) r=mid;
else l=mid;
}
res=mn(cur[l].ft,cur[l].sc+tag);
if (l+1<cur.size())
res=mx(res,mn(cur[l+1].ft,cur[l+1].sc+tag));
return res;
}
int solve(int l,int r,int x){
int cur=x,ans=x,tem;
if (belong[l]==belong[r]){
for (int i=l;i<=r;++i)
cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
return ans;
}
for (int i=l;i<=R[belong[l]];++i)
cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
cur=mx(cur,x);
for (int i=belong[l]+1;i<belong[r];i++){
tem=find(Pre[i],cur);
ans=mx(ans,tem);
tem=find(Vec[i],x);
ans=mx(ans,tem);
cur=mn(S(L[i],R[i]),G(L[i],R[i])+cur);
tem=find(Suf[i],x);
cur=mx(cur,tem);cur=mx(cur,x);
}
for (int i=L[belong[r]];i<=r;++i)
cur=mn(mx(cur,x)+D[i],T[i]),ans=mx(ans,cur);
return ans;
}
int main(){
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
scanf("%d",D+i),
SD[i]=SD[i-1]+D[i];
for (int i=1;i<=n;++i)
scanf("%d",T+i);
prepare();
init();
while(m--){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",solve(l,r,x));
}
return 0;
}