codeforces1452 E. Two Editorials

E. Two Editorials

官方题解
首先将每个参赛者按照区间中点排序，那么前一段参赛者听第一个人，而后一段听第二个人的。
预处理数组su[j]表示 j → m j\to m j→m这些参赛者能被“覆盖”最多“贡献”
只需要枚举第一个人演讲的区间，再考虑前多少参赛者听第一个人演讲，然后其余的参赛者听第二个人演讲（通过预处理数组直接查询）

//O(mlogm+nm)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll mod=998244353;
const int N=2020;
struct node
{
    int l,r;
    bool operator<(const node& O)const 
    {
        return l+r<O.l+O.r;
    }
}seg[N];
int n,m,k;
int su[N];
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        for(int i=1;i<=m;i++) cin>>seg[i].l>>seg[i].r;
        sort(seg+1,seg+1+m);
        
        for(int i=1;i+k-1<=n;i++)
        {
            int cur=0;
            for(int j=m;j;j--)
            {
                cur+=max(0,min(i+k-1,seg[j].r)-max(i,seg[j].l)+1);
                su[j]=max(su[j],cur);
            }
        }
        int res=su[1];
        for(int i=1;i+k-1<=n;i++)
        {
            int cur=0;
            for(int j=1;j<=m;j++)
            {
                cur+=max(0,min(i+k-1,seg[j].r)-max(i,seg[j].l)+1);
                res=max(res,cur+su[j+1]);
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

总结：没有挖掘到按照中点排序的性质，以及预处理优化做的太少！