UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214436#2767. 摆烂a_sad_soul308ms1244kbC++111.1kb2024-11-18 21:37:592024-11-19 08:35:10

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e6+10;
ll f[MAXN];
int n;
ll a[MAXN],t[MAXN];
struct node{
    int i;ll a;
}nxt[MAXN];
node max(node a,node b){
    if(a.a==b.a){
        if(a.i<b.i)return b;
        return a;
    }
    if(a.a<b.a)return b;
    return a;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&t[i],&a[i]);
        nxt[i].i=i,nxt[i].a=a[i];
    }
    //if(n<=2000){
    for(int i=1;i<=n;++i){
        ll mx=a[i];
        f[i]=2e18;
        for(int j=i-1;~j;--j){
            f[i]=min(f[i],max(f[j],t[i])+mx*2);
            mx=max(mx,a[j]);
        }
    }
    printf("%lld\n",f[n]);
    return 0;
    //}
    for(int i=n-1;i;--i){
        nxt[i]=max(nxt[i],nxt[i+1]);
    }
    ll nt=0;
    int l=1;
    while(l<=n){
        int p=max(nxt[l].i,(int)(lower_bound(t+1,t+1+n,nt)-t));
        ll mxa=0;
        for(int j=l;j<=p;++j)mxa=max(mxa,a[j]);
        nt=max(t[p],nt)+mxa*2;
        l=p+1;
        while(t[l]==t[p])++l;
    }
    printf("%lld\n",nt);
    return 0;
}

Details

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

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1200kb

input:

20
12513359 382258501
49946422 294259408
61782741 259996549
128874560 457675284
152578248 511428369
...

output:

2781551734

result:

ok 1 number(s): "2781551734"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

20
6592046 616393821
8538879 124771654
24979050 168650283
59952328 506075107
128878498 796836890
168...

output:

2878186356

result:

ok 1 number(s): "2878186356"

Test #3:

score: 0
Accepted
time: 1ms
memory: 1204kb

input:

20
2099663 147467539
25290040 156795746
197254068 590585918
198843927 512239904
222920966 456981246
...

output:

2770880243

result:

ok 1 number(s): "2770880243"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1200kb

input:

20
66393530 420843093
90129695 489656570
131248562 182208891
291691534 751771331
342922878 673384475...

output:

2926027520

result:

ok 1 number(s): "2926027520"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

20
141852945 69130050
155003677 784901688
156591867 730149439
161520357 619098795
188670057 61380271...

output:

2878920725

result:

ok 1 number(s): "2878920725"

Test #6:

score: 0
Accepted
time: 1ms
memory: 1204kb

input:

20
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 333333326
8...

output:

888888906

result:

ok 1 number(s): "888888906"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1208kb

input:

20
0 200000000
1 199999999
2 199999998
3 199999997
4 199999996
5 199999995
6 199999994
7 199999993
8...

output:

799218728

result:

ok 1 number(s): "799218728"

Subtask #2:

score: 20
Accepted

Test #8:

score: 20
Accepted
time: 0ms
memory: 1240kb

input:

1000
132699 718470029
234343 395421925
1290414 393017296
1399642 607415822
1402810 515471990
2008288...

output:

2991845504

result:

ok 1 number(s): "2991845504"

Test #9:

score: 0
Accepted
time: 1ms
memory: 1236kb

input:

1000
1460927 635822050
1474184 113973702
2262058 184319286
2754182 45688636
3158543 762355475
357426...

output:

2997073536

result:

ok 1 number(s): "2997073536"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1236kb

input:

1000
2118442 141038751
2135116 387165975
4874198 290249307
6872737 82266843
7401335 726603624
756080...

output:

2995302771

result:

ok 1 number(s): "2995302771"

Test #11:

score: 0
Accepted
time: 0ms
memory: 1236kb

input:

1000
437090 934565437
1175198 156863320
1198404 324764019
2277385 373440655
2425307 392581950
350360...

output:

2995901355

result:

ok 1 number(s): "2995901355"

Test #12:

score: 0
Accepted
time: 1ms
memory: 1240kb

input:

1000
9066 773817477
123486 806680042
851047 596461942
992394 523789453
1003388 520126158
1323726 958...

output:

2992153228

result:

ok 1 number(s): "2992153228"

Test #13:

score: 0
Accepted
time: 0ms
memory: 1240kb

input:

1000
1219327 803904616
2680619 571390377
2920737 199860734
3524708 883722438
4171344 134002719
59874...

output:

2997734121

result:

ok 1 number(s): "2997734121"

Test #14:

score: 0
Accepted
time: 0ms
memory: 1240kb

input:

1000
2880284 488746460
3414969 562543737
4498732 74314414
9375222 111266686
9458421 596112995
963592...

output:

2998591235

result:

ok 1 number(s): "2998591235"

Test #15:

score: 0
Accepted
time: 2ms
memory: 1240kb

input:

1000
1239163 666132179
1871097 706139536
2956078 487495665
3259471 69911742
4479955 188362973
586756...

output:

2996854561

result:

ok 1 number(s): "2996854561"

Test #16:

score: 0
Accepted
time: 0ms
memory: 1236kb

input:

1000
630980 355641503
934118 736144505
1523728 365898752
4057089 829930253
4910133 224420115
4990452...

output:

2999709988

result:

ok 1 number(s): "2999709988"

Test #17:

score: 0
Accepted
time: 0ms
memory: 1236kb

input:

1000
193594 350732868
965625 322880549
1694055 576483511
1992769 754390117
2507741 171984733
3271204...

output:

2999420445

result:

ok 1 number(s): "2999420445"

Test #18:

score: 0
Accepted
time: 2ms
memory: 1240kb

input:

1000
0 333333333
1 333333332
2 333333331
3 333333330
4 333333329
5 333333328
6 333333327
7 333333326...

output:

888889886

result:

ok 1 number(s): "888889886"

Test #19:

score: 0
Accepted
time: 0ms
memory: 1244kb

input:

1000
0 200000000
1 199999999
2 199999998
3 199999997
4 199999996
5 199999995
6 199999994
7 199999993...

output:

799217760

result:

ok 1 number(s): "799217760"

Subtask #3:

score: 0
Time Limit Exceeded

Test #20:

score: 0
Time Limit Exceeded

input:

100000
9326 430414358
13368 156324232
15149 550951304
22296 345034579
22578 397947033
37137 49312905...

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #32:

score: 0
Time Limit Exceeded

input:

2000000
181 24185667
293 532288461
1433 921996635
1694 629544979
2540 173534643
2662 963172401
3159 ...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #42:

score: 0
Time Limit Exceeded

input:

2000000
684 624071334
1181 709831992
1397 43325781
1938 430417709
4157 60566309
4568 912818933
5265 ...

output:


result: