ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214522 | #574. t3 | erican | 0 | 18ms | 2804kb | C++11 | 2.7kb | 2024-11-19 20:16:02 | 2024-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'