QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85261#366. Long Distance Coachlmeowdn0 5ms16064kbC++141.8kb2023-03-07 14:29:482023-03-07 14:29:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 14:29:49]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:16064kb
  • [2023-03-07 14:29:48]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=1e6+9;
int X,n,m,w,a[N],T,s[N],t[N],g[N],st[N],top,f[N],c[N],y[N];
pii p[N];

bool cmpc(int a,int b,int c) {
    return (y[a]-y[b])*(b-c)<(y[b]-y[c])*(a-b);
}
bool cmpk(int a,int b,int k) {
    return y[a]-y[b]<k*(b-a);
}

signed main() {
    X=read(), n=read(), m=read(), w=read(), T=read();
    rep(i,1,n) s[i]=read(); s[++n]=X;
    rep(i,1,m) p[i].fi=read(), p[i].se=read();
    sort(p+1,p+m+1);
    rep(i,1,m) c[i]=c[i-1]+p[i].se;
    rep(i,1,m) a[i]=s[n]/T+(p[i].fi<=s[n]%T);
    rep(i,1,m) t[i]=p[i].fi, g[i]=a[i];
    rep(i,1,n) {
        int p=lower_bound(t,t+m+1,s[i]%T)-t-1;
        if(p) g[p]=min(g[p],s[i]/T);
    }
    f[0]=w*(s[n]/T+1), y[0]=f[0], st[++top]=0;
    rep(i,1,m) {
        f[i]=f[i-1]+a[i]*w;
        int l=2,r=top,res=y[0];
        while(l<=r) {
            int mid=l+r>>1; res=min(res,y[st[mid]]-w*g[i]*st[mid]);
            if(cmpk(st[mid-1],st[mid],w*g[i])) l=mid+1;
            else r=mid-1;
        }
        f[i]=min(f[i],res+w*g[i]*i+c[i]);
        y[i]=f[i]-c[i];
        while(top>1&&!cmpc(st[top-1],st[top],i)) top--;
        st[++top]=i;
    }
    printf("%lld\n",f[m]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 16
Accepted
time: 2ms
memory: 15892kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 0
Accepted
time: 5ms
memory: 15852kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

score: 0
Accepted
time: 5ms
memory: 15880kb

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

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

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

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

input:

142 4 7 10 13
67
44
86
141
3 1000000000
6 1000000000
9 1000000000
1 60
4 81
7 48
10 14

output:

878

result:

ok single line: '878'

Test #6:

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

input:

142 3 8 10 13
68
46
37
4 1000000000
8 1000000000
1 61
2 59
5 79
6 79
9 20
10 155

output:

982

result:

ok single line: '982'

Test #7:

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

input:

150 8 8 10 18
5
88
75
87
83
14
109
112
17 30
7 70
2 24
10 25
12 34
9 92
8 30
13 18

output:

463

result:

ok single line: '463'

Test #8:

score: -16
Wrong Answer
time: 1ms
memory: 16064kb

input:

10000000000 8 8 6 18
9547257284
4226673527
9454195771
9513946487
7287482436
6692534804
3951479147
8774939403
12 415893810
4 735304001
13 184845346
14 354080601
15 455062532
16 886416267
3 985580216
1 97417991

output:

18719063460

result:

wrong answer 1st lines differ - expected: '18443869092', found: '18719063460'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%