ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214526 | #574. t3 | Running_a_way | 0 | 39ms | 2480kb | C++11 | 2.9kb | 2024-11-19 20:30:24 | 2024-11-19 23:02:02 |
answer
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 100010;
int n; ll X, Y, Z;
int a[N], b[N];
namespace subtask2 {
priority_queue<pii, vector<pii>, greater<pii>> q;
void main() {
// printf("In sub2:\n");
for (int i = 1; i <= n; i++)
if(a[i] > b[i]) q.push({i, a[i] - b[i]});
ll eps1 = 0, eps2 = 0, ans = 0;
for (int i = 1; i <= n; i++) {
if(a[i] >= b[i]) continue;
ll delta = b[i] - a[i];
while(q.size() && q.top().second <= delta) {
delta -= q.top().second;
ans += 1ll * abs(i - q.top().first) * q.top().second;
q.pop();
}
if(delta && q.size()) {
pii pr = q.top(); q.pop();
ans += 1ll * abs(i - pr.first) * delta;
q.push({pr.first, pr.second - delta});
delta = 0;
}
if(delta) eps1 += delta;
}
while(q.size()) eps2 += q.top().second, q.pop();
if(eps1) ans += X * eps1;
if(eps2) ans += Y * eps2;
printf("%lld\n", ans);
}
}
namespace subtaskall {
priority_queue<pii> q1, q2; // q1 存溢出,q2 存缺少,第一维放坐标,第二维放 size
void main() {
ll ans = 0;
for (int i = 1; i <= n; i++) {
if(a[i] < b[i]) {
int delta = b[i] - a[i];
while(q1.size() && delta) {
int j = q1.top().first, D = q1.top().second, d1 = min(q1.top().second, delta);
if((i - j) * Z > X + Y) ans += d1 * (X + Y);
else ans += d1 * (i - j) * Z;
delta -= d1;
q1.pop();
if(D > d1) q1.push({j, D - d1});
}
if(delta) q2.push({i, delta});
} else if(a[i] > b[i]) {
int delta = a[i] - b[i];
while(q2.size() && delta) {
int j = q2.top().first, D = q2.top().second, d1 = min(q2.top().second, delta);
if((i - j) * Z > X + Y) ans += d1 * (X + Y);
else ans += d1 * (i - j) * Z;
delta -= d1;
q2.pop();
if(D > d1) q2.push({j, D - d1});
}
if(delta) q1.push({i, delta});
}
}
while(q2.size()) ans += X * q2.top().second, q2.pop();
while(q1.size()) ans += Y * q1.top().second, q1.pop();
printf("%lld\n", ans);
}
}
int main() {
// freopen("A1.in", "r", stdin);
// freopen("A.out", "w", stdout);
scanf("%d%lld%lld%lld", &n, &X, &Y, &Z);
for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
if(X == Y && X == 1e8 && Z == 1) subtask2::main();
else subtaskall::main();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1248kb
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:
15566
result:
wrong answer 1st words differ - expected: '12399', found: '15566'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 21ms
memory: 2480kb
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:
211756751567
result:
wrong answer 1st words differ - expected: '211716275189', found: '211756751567'
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 18ms
memory: 2024kb
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:
12891090912
result:
wrong answer 1st words differ - expected: '11782941072', found: '12891090912'