cf1452E

题意

Link

题解

hint1

如果只有一个老师的话，很好算。

hint2

我们可以通过算每一个学生的贡献，算出总体答案。

sol

枚举第一个老师的左端点。

算每一个同学对第二个老师放的位置的贡献。

很容易发现这个贡献是两段等差数列，那么我们可以差分两次维护。

复杂度

\(\mathcal{O(nm)}\)

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int N=2000+100;
int l[N],r[N];
int sum[N],ans=0;
int f[N],cf[N];
inline void modify(int x,int y,int v){
    if(x>y) return ;
    cf[x]+=v,cf[y+1]-=v;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n-k+1;i++){
        memset(sum,0,sizeof(sum));
        memset(f,0,sizeof(f));
        memset(cf,0,sizeof(cf));
        for(int j=i;j<=i+k-1;j++) sum[j]=sum[j-1]+1;
        for(int j=i+k;j<=n;j++) sum[j]=sum[j-1];
        int res=0;
        for(int j=1;j<=m;j++) res+=sum[r[j]]-sum[l[j]-1];
        int x=i,y=i+k-1;
        for(int j=1;j<=m;j++){
            if(y<l[j]) {
                modify(l[j]-k+1,min(l[j],r[j]-k+1),1);
                modify(max(l[j],r[j]-k+1)+1,r[j]+1,-1);
            }
            else if(l[j]<=y&&r[j]>y){
                modify(x+1,min(l[j],r[j]-k+1),1);
                modify(max(l[j],r[j]-k+1)+1,r[j]-(y-l[j]),-1);
            }
        }
        int tmp=0;
        for(int j=1;j<=n;j++){
            cf[j]+=cf[j-1];
            tmp+=cf[j];
            ans=max(ans,res+tmp);
        }
    }
    cout<<ans;
}