UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214522#574. t3erican018ms2804kbC++112.7kb2024-11-19 20:16:022024-11-19 23:01:36

answer

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;
// #define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
// void write(int out) {
// 	if (out < 0)
// 		putchar('-'), out = -out;
// 	if (out > 9)
// 		write(out / 10);
// 	putchar(out % 10 + '0');
// }
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

// int f[N][N];//整理好前i个,且需要后面补充j个时的最小代价(j<0代表溢出到后面)
/*
反悔贪心

*/



priority_queue<pii> pa,pb; // <id,tot>
int ans;
int a[N],b[N];

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int n=rd,X=rd,Y=rd,Z=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
        b[i]=rd;
    }
    // for(int i=1;i<=n;i++){
    //     b[i]=rd;
    // }


    for(int i=1;i<=n;i++){
        if(a[i]==b[i])continue;
        if(a[i]<b[i]){
            while(a[i]<b[i]&&pa.size()&&(i-pa.top().pf)*Z<X){
                int x=pa.top().pf;
                int y=pa.top().ps;
                pa.pop();
                int c=min(b[i]-a[i],y);
                a[i]+=c;
                ans+=(i-x)*Z*c;
                ans-=Y*c;
                y-=c;
                if(y)pa.push({x,y});
                
            }
            if(a[i]<b[i]){
                ans+=X*(b[i]-a[i]);
                pb.push({i,b[i]-a[i]});
                a[i]=b[i];
            }
        }else{
            while(a[i]>b[i]&&pb.size()&&(i-pb.top().pf)*Z<Y){
                int x=pb.top().pf;
                int y=pb.top().ps;
                pb.pop();
                int c=min(a[i]-b[i],y);
                a[i]-=c;
                ans+=(i-x)*Z*c;
                ans-=X*c;
                y-=c;
                if(y)pb.push({x,y});
                
            }
            if(a[i]>b[i]){
                ans+=Y*(a[i]-b[i]);
                pa.push({i,a[i]-b[i]});
                a[i]=b[i];
            }
        }


    }
    cout<<ans<<endl;
}

Details

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1208kb

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: 8ms
memory: 2804kb

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:

211720592186

result:

wrong answer 1st words differ - expected: '211716275189', found: '211720592186'

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 10ms
memory: 2780kb

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'