QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488838#9127. Optimal Train Operationucup-team1525WA 3ms28788kbC++171.8kb2024-07-24 15:41:292024-07-24 15:41:29

Judging History

你现在查看的是最新测评结果

  • [2024-07-24 15:41:29]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:28788kb
  • [2024-07-24 15:41:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using i128=__int128;
const int N=5e5;
const ll inf=1ll<<60;
int n;
int c[N+5],a[N+5];
ll f[N+5];
struct Line{
    ll k,b;
    Line(ll k=0,ll b=0):k(k),b(b){}
    ll eval(ll x){ return k*x+b; }
}line[N+5];
bool chk1(Line x,Line y,Line z){
    return (i128)(z.k-x.k)*(x.b-y.b)<=(i128)(y.k-x.k)*(x.b-z.b);
}
bool chk2(Line x,Line y,Line z){
    return (i128)(x.k-z.k)*(y.b-x.b)>=(i128)(x.k-y.k)*(z.b-x.b);
}
void solve(int l,int r){
    if(l==r){
        f[l]+=a[l];
        return;
    }
    int mid=l+r>>1;
    solve(l,mid);
    static int pre[N+5],suf[N+5];
    suf[mid]=0; pre[mid]=0;
    for(int i=mid-1;i>=l;i--)
        suf[i]=max(suf[i+1],c[i+1]);
    for(int i=mid+1;i<=r;i++)
        pre[i]=max(pre[i-1],c[i]);
    static Line s[N+5];
    int sr=0;
    for(int i=l;i<=mid;i++)
        line[i]=Line(suf[i],f[i]-1ll*i*suf[i]);
    for(int i=r,j=l;i>mid;i--){
        while(j<=mid&&suf[j]>=pre[i]){
            while(sr>1&&chk1(line[j],s[sr],s[sr-1])) sr--;
            s[++sr]=line[j]; j++;
        }
        while(sr>1&&s[sr].eval(i)>=s[sr-1].eval(i)) sr--;
        if(sr) f[i]=min(f[i],s[sr].eval(i));
    }
    for(int i=l;i<=mid;i++)
        line[i]=Line(-i,f[i]);
    sr=0;
    for(int i=mid+1,j=mid;i<=r;i++){
        while(j>=l&&suf[j]<pre[i]){
            while(sr>1&&chk2(line[j],s[sr],s[sr-1])) sr--;
            s[++sr]=line[j]; j--;
        }
        while(sr>1&&s[sr].eval(pre[i])>=s[sr-1].eval(pre[i])) sr--;
        if(sr) f[i]=min(f[i],s[sr].eval(pre[i])+1ll*i*pre[i]);
    }
    solve(mid+1,r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    fill(f+1,f+1+n,inf);
    solve(0,n);
    printf("%lld\n",f[n]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 27300kb

input:

4
3 1 4 1
5 9 2

output:

15

result:

ok "15"

Test #2:

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

input:

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

output:

682

result:

ok "682"

Test #3:

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

input:

7
476190629 262703497 211047202 971407775 628894325 731963982 822804784
877914575 602436426 24979445 861648772 623690081 433933447

output:

5339182432

result:

ok "5339182432"

Test #4:

score: 0
Accepted
time: 3ms
memory: 28028kb

input:

8
910286918 802329211 404539679 303238506 317063340 492686568 773361868 125660016
430302156 982631932 161735902 880895728 923078537 707723857 189330739

output:

6166732840

result:

ok "6166732840"

Test #5:

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

input:

5
191890310 576823355 782177068 404011431 818008580
839296263 462224593 492601449 384836991

output:

4069897043

result:

ok "4069897043"

Test #6:

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

input:

6
138996221 501899080 353195922 545531545 910748511 350034067
160449218 155374934 840594328 164163676 797829355

output:

3921700772

result:

ok "3921700772"

Test #7:

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

input:

2
824284691 533206504
470338674

output:

1648569382

result:

ok "1648569382"

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 28600kb

input:

4524
43 144 216 44 156 252 243 172 78 246 56 103 207 177 102 22 202 236 61 255 128 238 237 187 176 110 156 213 65 11 75 239 142 9 203 124 154 149 119 59 152 91 151 226 131 184 174 236 220 149 16 209 51 32 40 131 119 138 201 171 249 150 108 82 75 70 204 80 131 42 180 125 257 131 5 107 39 145 154 242 ...

output:

894178

result:

wrong answer 1st words differ - expected: '892773', found: '894178'