ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214544 | #574. t3 | naroto2022 | 100 | 728ms | 3040kb | C++ | 1.7kb | 2024-11-19 22:01:32 | 2024-11-19 23:04:01 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int MM=5005,MN=1e5+5;
ll a[MM],b[MM],la,lb,dp[MM][MM],x,y,z,n,c[2],ans;
bool op;
priority_queue<ll> q[2];
void write(ll n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
int main(){
n=read();x=read();y=read();z=read();
if(n<=5000){
for(int i=1; i<=n; i++){
ll num;
num=read();while(num){a[++la]=i;num--;}
num=read();while(num){b[++lb]=i;num--;}
}
for(int i=0; i<=lb; i++) dp[0][i]=i*x;
for(int i=0; i<=la; i++) dp[i][0]=i*y;
for(int i=1; i<=la; i++) for(int j=1; j<=lb; j++){
dp[i][j]=i*y+j*x;
dp[i][j]=min(dp[i][j],dp[i][j-1]+x);
dp[i][j]=min(dp[i][j],dp[i-1][j]+y);
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+z*abs(a[i]-b[j]));
}
write(dp[la][lb]);putchar('\n');
return 0;
}
c[0]=y;c[1]=x;
for(int i=1; i<=n; i++){
ll u=read(),v=read();
if(u==v) continue;
op=u>v;
for(int j=1; j<=abs(u-v); j++){
if(q[op^1].empty()||i*z-q[op^1].top()>c[op^1]){
ans+=c[op^1];
q[op].push(i*z+c[op^1]);
}
else{
ans+=i*z-q[op^1].top();
q[op].push(2*i*z-q[op^1].top()),q[op^1].pop();
}
}
}
write(ans);putchar('\n');
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 2608kb
input:
50 4 401 83 1 9 0 10 1 1 7 5 6 2 6 10 5 10 5 5 4 4 10 8 8 3 4 8 8 0 1 2 8 9 9 9 4 6 8 7 3 10 2 4 9 3...
output:
12399
result:
ok "12399"
Test #2:
score: 0
Accepted
time: 0ms
memory: 2456kb
input:
50 1811 650 156 6 5 3 1 0 9 0 0 1 0 0 7 1 10 10 3 8 10 5 9 8 6 2 9 1 4 0 9 2 9 9 3 2 3 5 2 4 6 1 2 9...
output:
85235
result:
ok "85235"
Test #3:
score: 0
Accepted
time: 0ms
memory: 2468kb
input:
50 3618 899 582 1 2 5 3 10 7 3 6 6 9 5 4 7 10 4 0 1 4 1 9 8 9 10 10 6 9 0 5 6 9 9 8 0 10 1 8 6 2 0 1...
output:
253368
result:
ok "253368"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3040kb
input:
50 425 1148 8 6 9 8 5 10 4 6 0 0 7 10 0 3 0 9 9 5 10 7 9 8 1 8 0 10 3 10 1 10 9 9 3 8 6 8 3 7 8 10 7...
output:
65368
result:
ok "65368"
Test #5:
score: 0
Accepted
time: 0ms
memory: 2756kb
input:
50 2232 2750 434 1 6 0 7 9 1 9 6 6 5 4 8 9 0 3 7 9 5 2 10 9 5 5 1 3 7 9 8 3 8 9 8 6 3 4 9 9 4 9 4 10...
output:
121406
result:
ok "121406"
Test #6:
score: 0
Accepted
time: 0ms
memory: 2680kb
input:
50 4039 2999 507 6 2 3 9 8 10 1 0 0 4 9 5 5 0 8 4 2 10 9 10 9 8 3 2 8 1 9 4 8 8 9 2 4 10 1 4 0 0 8 2...
output:
224049
result:
ok "224049"
Test #7:
score: 0
Accepted
time: 0ms
memory: 2428kb
input:
50 846 3248 933 1 10 5 10 8 7 4 6 6 2 3 2 0 0 2 2 6 5 4 0 9 0 0 3 1 5 8 0 1 8 9 7 1 6 8 10 1 7 7 10 ...
output:
174023
result:
ok "174023"
Test #8:
score: 0
Accepted
time: 2ms
memory: 2712kb
input:
50 2653 3497 359 6 6 8 1 7 4 7 1 0 0 8 10 7 1 7 10 10 10 10 0 9 3 9 4 6 10 7 7 5 8 9 2 10 3 4 5 3 2 ...
output:
330818
result:
ok "330818"
Test #9:
score: 0
Accepted
time: 2ms
memory: 2676kb
input:
50 4460 3746 785 1 3 0 3 6 2 10 6 6 9 2 7 2 1 1 8 3 5 6 0 9 6 6 4 10 4 7 3 9 7 9 7 8 10 0 0 5 9 6 4 ...
output:
203160
result:
ok "203160"
Test #10:
score: 0
Accepted
time: 0ms
memory: 2496kb
input:
50 1267 3995 858 6 10 3 5 6 10 2 1 0 7 7 4 9 1 6 6 7 0 1 1 9 9 4 5 3 8 6 0 3 7 9 1 5 7 8 6 6 5 5 2 0...
output:
221209
result:
ok "221209"
Subtask #2:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 36ms
memory: 1408kb
input:
100000 100000000 100000000 1 4 1 7 1 7 6 7 5 7 5 6 6 5 1 1 4 2 0 3 0 5 7 1 9 1 1 6 8 2 5 7 7 7 9 6 3...
output:
211716275189
result:
ok "211716275189"
Test #12:
score: 0
Accepted
time: 35ms
memory: 1356kb
input:
100000 100000000 100000000 1 3 2 6 7 3 8 9 4 5 8 1 0 4 6 9 0 2 5 1 4 0 2 2 9 5 10 7 1 6 4 3 0 7 9 1 ...
output:
146913863207
result:
ok "146913863207"
Test #13:
score: 0
Accepted
time: 36ms
memory: 1320kb
input:
100000 100000000 100000000 1 2 2 5 1 0 0 0 4 2 0 7 6 2 0 6 6 2 10 10 8 5 9 2 9 8 7 8 5 0 4 10 4 6 9 ...
output:
125015898506
result:
ok "125015898506"
Test #14:
score: 0
Accepted
time: 38ms
memory: 1588kb
input:
100000 100000000 100000000 1 1 3 5 7 7 3 2 3 10 3 1 0 0 5 3 2 3 4 7 1 0 4 3 9 0 5 9 10 4 3 6 9 6 9 0...
output:
306911415038
result:
ok "306911415038"
Test #15:
score: 0
Accepted
time: 38ms
memory: 1376kb
input:
100000 100000000 100000000 1 0 4 4 1 4 6 4 2 8 6 7 6 9 10 0 8 3 9 5 5 5 10 3 9 3 2 10 3 9 2 2 2 6 9 ...
output:
83822988893
result:
ok "83822988893"
Test #16:
score: 0
Accepted
time: 38ms
memory: 1348kb
input:
100000 100000000 100000000 1 10 5 3 7 0 9 6 2 5 9 2 0 7 4 8 3 3 3 2 8 0 6 3 9 6 10 0 7 3 2 9 6 5 9 0...
output:
17837967511
result:
ok "17837967511"
Test #17:
score: 0
Accepted
time: 35ms
memory: 1424kb
input:
100000 100000000 100000000 1 9 6 2 1 8 0 8 1 2 2 7 6 5 9 5 10 4 8 0 1 6 1 4 9 9 8 1 1 7 1 5 10 5 9 5...
output:
146418351385
result:
ok "146418351385"
Test #18:
score: 0
Accepted
time: 38ms
memory: 1324kb
input:
100000 100000000 100000000 1 8 7 2 7 4 3 10 0 0 5 2 0 4 3 2 5 4 2 9 5 0 7 4 9 2 5 2 5 1 0 1 4 5 9 10...
output:
84017584381
result:
ok "84017584381"
Test #19:
score: 0
Accepted
time: 35ms
memory: 1412kb
input:
100000 100000000 100000000 1 7 8 1 1 0 6 1 0 8 8 7 6 2 8 10 1 4 7 6 9 6 3 5 10 5 3 3 9 5 0 8 8 5 8 4...
output:
18421668749
result:
ok "18421668749"
Test #20:
score: 0
Accepted
time: 34ms
memory: 1352kb
input:
100000 100000000 100000000 1 6 8 0 7 8 9 3 10 5 0 2 0 0 2 7 7 5 1 4 2 0 9 5 10 8 0 3 3 10 10 4 1 4 8...
output:
71718994500
result:
ok "71718994500"
Subtask #3:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 33ms
memory: 1344kb
input:
100000 30694440 93757838 144 1 4 0 5 9 3 3 8 6 9 7 4 3 5 6 1 6 6 4 5 10 0 9 4 7 4 9 1 5 4 8 4 2 0 10...
output:
11782941072
result:
ok "11782941072"
Test #22:
score: 0
Accepted
time: 38ms
memory: 1404kb
input:
100000 13169689 16407911 951 7 1 3 7 9 0 6 2 0 7 1 0 9 5 0 10 10 1 0 6 10 3 6 5 0 8 8 8 9 4 8 9 10 7...
output:
66599332884
result:
ok "66599332884"
Test #23:
score: 0
Accepted
time: 33ms
memory: 1324kb
input:
100000 95644938 91574337 758 2 8 6 9 8 8 9 8 6 5 6 8 5 6 5 8 3 6 6 6 10 6 4 6 5 2 8 4 3 4 8 4 8 3 3 ...
output:
82965110631
result:
ok "82965110631"
Test #24:
score: 0
Accepted
time: 38ms
memory: 1364kb
input:
100000 78120187 66740763 565 7 5 9 0 7 5 1 3 0 4 0 5 0 6 10 5 7 1 1 7 10 9 1 7 9 6 7 0 7 3 8 9 6 0 1...
output:
35524028010
result:
ok "35524028010"
Test #25:
score: 0
Accepted
time: 32ms
memory: 1588kb
input:
100000 60595436 41907189 372 2 1 1 2 6 3 4 8 6 2 5 2 7 6 4 3 0 6 8 7 10 2 10 8 2 0 6 7 0 3 8 3 3 7 6...
output:
77303496819
result:
ok "77303496819"
Test #26:
score: 0
Accepted
time: 36ms
memory: 1392kb
input:
100000 43070685 64557262 179 7 9 3 4 6 0 7 3 0 0 10 10 2 7 9 1 4 1 3 7 10 5 7 9 7 4 6 3 4 3 8 8 1 3 ...
output:
57824985320
result:
ok "57824985320"
Test #27:
score: 0
Accepted
time: 39ms
memory: 1412kb
input:
100000 25545934 39723688 986 2 5 6 6 5 8 10 8 6 9 4 7 9 7 3 9 8 6 9 8 10 8 5 10 0 9 5 10 9 3 8 3 10 ...
output:
42292679046
result:
ok "42292679046"
Test #28:
score: 0
Accepted
time: 40ms
memory: 1380kb
input:
100000 60537536 14890114 793 7 2 9 7 4 6 2 3 0 7 8 4 4 7 8 7 1 1 4 8 10 0 2 0 4 3 4 6 2 2 8 8 7 7 6 ...
output:
45040697924
result:
ok "45040697924"
Test #29:
score: 0
Accepted
time: 38ms
memory: 1408kb
input:
100000 25488034 12706613 407 7 6 3 0 3 0 8 3 0 4 7 9 6 8 7 2 9 1 6 9 10 6 8 2 2 1 3 9 10 2 8 7 3 0 9...
output:
57925341606
result:
ok "57925341606"
Test #30:
score: 0
Accepted
time: 34ms
memory: 1320kb
input:
100000 7963283 87873039 214 2 2 6 2 2 9 0 9 5 2 1 6 2 8 1 0 1 7 1 9 10 10 6 2 6 5 2 5 4 2 8 2 0 7 6 ...
output:
83824996000
result:
ok "83824996000"