ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214543 | #574. t3 | naroto2022 | 30 | 4ms | 3060kb | C++ | 1.0kb | 2024-11-19 21:50:43 | 2024-11-19 23:03:57 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MM=1005,MN=1e5+5;
ll a[MM],b[MM],la,lb,dp[MM][MM],x,y,z,n;
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();
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;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 0ms
memory: 2620kb
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: 1ms
memory: 2464kb
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: 2ms
memory: 2476kb
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: 3060kb
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: 2764kb
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: 2688kb
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: 1ms
memory: 2436kb
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: 0ms
memory: 2744kb
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: 0ms
memory: 2696kb
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: 2508kb
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: 0
Runtime Error
Test #11:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
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...