ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214545 | #574. t3 | nodgd | 0 | 34ms | 3120kb | C++11 | 2.0kb | 2024-11-19 22:03:04 | 2024-11-19 23:04:07 |
answer
#include <bits/stdc++.h>
using namespace std;
const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline int read_int() {
int x = 0;
char ch = read_char(), flag = 0;
while (ch != '-' && (ch < '0' || ch > '9')) {
ch = read_char();
}
if (ch == '-') {
flag = 1;
ch = read_char();
}
for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
x = x * 10 + (ch - '0');
}
return flag ? -x : x;
}
const int MAX_N = 100000 + 5;
int N, X, Y, Z;
int a[MAX_N], al[MAX_N], ar[MAX_N];
long long ans;
priority_queue<pair<int,int>> pq;
int main() {
N = read_int();
X = read_int(), Y = read_int(), Z = read_int();
for (int i = 1; i <= N; i ++) {
int aa = read_int(), bb = read_int();
a[i] = bb - aa;
al[i] = i - 1;
ar[i] = i + 1;
if (i > 1 && a[i] * a[i - 1] < 0) {
pq.push(make_pair(-1, i - 1));
}
}
auto rm = [&] (int i) {
if (al[i] >= 1) ar[al[i]] = ar[i];
if (ar[i] <= N) al[ar[i]] = al[i];
if (al[i] >= 1 && ar[i] <= N && a[al[i]] * a[ar[i]] < 0) {
pq.push(make_pair(al[i] - ar[i], al[i]));
}
};
while (pq.size()) {
auto tmp = pq.top();
pq.pop();
int i = tmp.second, j = ar[i];
if (j - i != -tmp.first) continue;
if (a[i] * a[j] >= 0) continue;
if (1ll * Z * (j - i) > X + Y) break;
int t = min(abs(a[i]), abs(a[j]));
ans += 1ll * Z * (j - i) * t;
if (a[i] < 0) {
a[i] += t, a[j] -= t;
} else {
a[i] -= t, a[j] += t;
}
if (!a[i]) rm(i);
if (!a[j]) rm(j);
}
for (int i = 1; i <= N; i ++) {
if (a[i] > 0) {
ans += X * a[i];
} else {
ans -= Y * a[i];
}
}
printf("%lld\n", ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1204kb
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:
13740
result:
wrong answer 1st words differ - expected: '12399', found: '13740'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 17ms
memory: 3120kb
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:
9360500347269
result:
wrong answer 1st words differ - expected: '211716275189', found: '9360500347269'
Subtask #3:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 17ms
memory: 3120kb
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:
5858771218756
result:
wrong answer 1st words differ - expected: '11782941072', found: '5858771218756'