NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214151	#2031. a	a_sad_soul	0	18ms	40748kb	C++11	1.5kb	2024-11-15 20:19:54	2024-11-15 23:26:06

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
const int INF = 1e9;
int L[MAXN],R[MAXN],cnt;
deque<int>q;
int ans=-1,mxR=-INF;
int n,k;
struct node{
    int l,r;
    bool operator<(const node x)const{
        return l<x.l;
    }
}a[MAXN];
int f[MAXN][101];
int main(){
    scanf("%d%d",&n,&k);
    memset(f,128,sizeof(f));
    for(int i=1;i<=n;++i)scanf("%d%d",&a[i].l,&a[i].r);//,--a[i].l;
    sort(a+1,a+1+n);
    for(int i=1;i<=n;++i){
        if(a[i].r>mxR){
            L[++cnt]=a[i].l,R[cnt]=a[i].r;mxR=a[i].r;
        }
    }k-=n-cnt;
    if(k<=0){
        ans=0;mxR=L[1];
        for(int i=1;i<=n;++i)ans+=R[i]-max(mxR,L[i]),mxR=R[i];
        printf("%d\n",ans);return 0;
    }
    for(int i=0;i<=k;++i)f[i][i]=0;
    for(int i=1;i<=n;++i){
        int x=1-i,sum=-INF;if(q.size())q.clear();
        for(int j=0;j<=min(k,cnt-i);++j){
            int l=j+k;
            while(!q.empty()&&R[q.front()]<=L[l]){
                sum=max(sum,f[q.front()][x+q.front()]),q.pop_front();
            }
            if(R[l-1]<=L[l])sum=max(sum,f[l-1][x+l-1]);
            else{
                while(q.size()&&f[q.back()][x+q.back()]-R[q.back()]<=f[l-1][x+l-1]-R[l-1])q.pop_back();
                q.push_back(l-1);
            }
            f[l][j]=sum-L[l]+R[l];
            if(q.size())f[l][j]=max(f[l][j],f[q.front()][x+q.front()]-R[q.front()]+R[l]);
        }
    }
    for(int i=cnt-k;i<=cnt;++i)ans=max(ans,f[i][k-cnt+i]);
    cout<<ans<<endl;
    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 0

Wrong Answer

time: 4ms

memory: 40708kb

input:

20 8
941374267 958239792
636546050 949277063
30572593 458894768
377940690 585510776
595907552 909524...

output:

-6353104

result:

wrong answer 1st lines differ - expected: '982023824', found: '-6353104'

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 40704kb

input:

20 15
76365869 433406218
633171333 786737074
131600137 929106040
44288699 688307921
419471992 769278...

output:

-5301374

result:

wrong answer 1st lines differ - expected: '923804666', found: '-5301374'

Test #3:

score: 0

Wrong Answer

time: 4ms

memory: 40708kb

input:

20 2
358841118 908572644
771680732 777280263
232627681 399317312
146158799 355582975
95552785 629032...

output:

-9923878

result:

wrong answer 1st lines differ - expected: '898648766', found: '-9923878'

Test #4:

score: 0

Wrong Answer

time: 3ms

memory: 40744kb

input:

5000 49
383739070 641316367
609140743 773905546
333655225 869528584
456526030 666877251
488787058 91...

output:

-154648

result:

wrong answer 1st lines differ - expected: '999604831', found: '-154648'

Test #5:

score: 0

Wrong Answer

time: 7ms

memory: 40744kb

input:

5000 56
6389143 923791616
594084401 918014476
192256209 434682769
125655174 766893261
348541120 7426...

output:

-35038

result:

wrong answer 1st lines differ - expected: '999844854', found: '-35038'

Test #6:

score: 0

Wrong Answer

time: 0ms

memory: 40748kb

input:

5000 63
206266865 481555569
431544412 914639759
535710313 662467481
77260492 436949450
208295182 418...

output:

-50252

result:

wrong answer 1st lines differ - expected: '999740177', found: '-50252'

Test #7:

score: 0

Runtime Error

input:

100000 95
31394575 31395303
35035434 35036166
64896609 64897277
10992021 10992677
17899328 17900254
...

output:

result:

Test #8:

score: 0

Runtime Error

input:

100000 83
233039267 233039367
916657359 916657459
864715109 864715209
936842396 936842496
562959930 ...

output:

result:

Test #9:

score: 0

Runtime Error

input:

100000 90
816642137 816642237
185449925 185450025
619425312 619425412
335954840 335954940
14523568 1...

output:

result:

Test #10:

score: 0

Runtime Error

input:

100000 85
932471751 932471851
591128329 591128429
632579047 632579147
902529780 902529880
377540930 ...