UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214519#574. t3Running_a_way058ms2484kbC++111.4kb2024-11-19 19:49:502024-11-19 23:01:11

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);
    }
}

int main() {
    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();
    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:

1012

result:

wrong answer 1st words differ - expected: '12399', found: '1012'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 27ms
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: 31ms
memory: 2484kb

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:

8755557683

result:

wrong answer 1st words differ - expected: '11782941072', found: '8755557683'