QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639775 | #8551. DFS Order 5 | argtarg | WA | 0ms | 3560kb | C++20 | 3.1kb | 2024-10-13 22:23:08 | 2024-10-13 22:23:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--)solve();
return 0;
}
//const int mod = 998244353;
void solve() {
int n;
int m;
cin>>n>>m;
vector<int>a(n+1),b(n+2);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
b[n+1]=1e18;
sort(b.begin()+1,b.end());
a.push_back(b[1]);
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
}
sort(a.begin()+1,a.end());
priority_queue<int,vector<int>,greater<int>>q1,q2;
queue<int>add;
for(int i=1;i<=n;i++){
if(b[i]>m)break;
auto t= lower_bound(a.begin()+1,a.end(),b[i]);
int pre1=0,pre2=0,pre3=0;
if(q1.size()&&q1.size()==i-1)pre1=q1.top();
auto it=t;
if(t!=a.end())pre2=*t-b[i];
if(t!=a.end()&&t!=a.begin()&&i!=1){
it--;
pre3=*t-*it;
}
vector<int>sz(n+1);
while(t!=a.end()&&(*t)<=min(m+1,b[i+1])){
int x=*t;
t++;
int y=m;
if((t!=a.end()))
y=*t;
if(y>min(m+1,b[i+1]))continue;
// cout<<"y== "<<y<<endl;
q1.push(y-x);
}
// cout<<q1.size()<<endl;
while(q1.size()>i){
q1.pop();
}
if(q1.size()&&pre1!=0){
if(q1.top()>pre1){
q1.push(pre3);
}
else {
// cout<<"i== "<<i<<endl;
// cout<<pre1<<' '<<pre2<<' '<<pre3<<endl;
// cout<<"sz-- "<<q1.size()<<endl;
int re=q1.top(),rre=pre1;
if(q1.size()<i){
re=0;
//rre=0;
}
int tmp=pre2-re;
int tmp2=-rre+pre3;
if(tmp2>tmp){
if(sz[i-1]==i-1){
while(q1.top()!=pre1){
add.push(q1.top());
q1.pop();
}
q1.pop();
while(add.size()){
q1.push(add.front());
add.pop();
}
}
q1.push(pre3);
}
else{
q1.push(pre2);
}
}
}
else{
q1.push(pre3);
}
// cout<<"-----------";cout<<pre1<<' '<<pre2<<' '<<pre3<<endl;
while(q1.size()>i){
q1.pop();
}
while(q1.size()&&q1.top()==0){
q1.pop();
}
sz[i]=q1.size();
}
int ans=0;
int sum=0;
while(q1.size()){
sum+=q1.top();
q1.pop();
}
ans=sum;
cout<<ans<<endl;
}
/*
2
3 13
6 7 13
1 9 999
4 14
6 7 13 14
1 9 999 999
3
3 10
1 5 9
1 2 3
3 10
1 5 9
1 1 4
3 10
1 5 9
1 5 10
*/
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3560kb
input:
6 7 1 2 1 3 2 4 3 5 2 6 2 4 1 2 4 2 2 4 3 2 4 4 2 4 5 2 4 6 6 1 2 6 4 3 5
output:
1 1 1 5 4 4
result:
wrong answer 1st words differ - expected: 'No', found: '1'