ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214435 | #2767. 摆烂 | a_sad_soul | 30 | 810ms | 63692kb | C++11 | 1.1kb | 2024-11-18 21:37:14 | 2024-11-19 08:35:05 |
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: 0ms
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: 1ms
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: 1200kb
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: 0ms
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: 0ms
memory: 1240kb
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: 2ms
memory: 1240kb
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: 2ms
memory: 1236kb
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: 1236kb
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: 1236kb
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: 1240kb
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: 1240kb
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: 3ms
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: 2ms
memory: 1240kb
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
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 16ms
memory: 4324kb
input:
100000 9326 430414358 13368 156324232 15149 550951304 22296 345034579 22578 397947033 37137 49312905...
output:
4682504635
result:
wrong answer 1st numbers differ - expected: '2999984291', found: '4682504635'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 407ms
memory: 63688kb
input:
2000000 181 24185667 293 532288461 1433 921996635 1694 629544979 2540 173534643 2662 963172401 3159 ...
output:
4698465128
result:
wrong answer 1st numbers differ - expected: '2999999604', found: '4698465128'
Subtask #5:
score: 0
Wrong Answer
Test #42:
score: 0
Wrong Answer
time: 375ms
memory: 63692kb
input:
2000000 684 624071334 1181 709831992 1397 43325781 1938 430417709 4157 60566309 4568 912818933 5265 ...
output:
4569895383
result:
wrong answer 1st numbers differ - expected: '2999999891', found: '4569895383'