UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214545#574. t3nodgd034ms3120kbC++112.0kb2024-11-19 22:03:042024-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;
}

Details

小提示:点击横条可展开更详细的信息

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'