QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#141354 | #6525. New Houses | cy1999 | TL | 1ms | 19276kb | C++20 | 1.4kb | 2023-08-17 11:03:45 | 2023-08-17 11:03:48 |
Judging History
answer
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define fr(a) freopen(a,"r",stdin)
#define fw(a) freopen(a,"w",stdout)
using namespace std;
typedef long long ll;
const int MAXN=5e5+10;
struct node{
ll a,b;
}zi[MAXN],lin[MAXN];
ll T,n,m,x,y;
ll tot1,tot2,ans,zizizi;
bool cmp(node a,node b){
return (a.a-a.b) < (b.a-b.b);
}
int main(){
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);
zizizi=ans=tot1=tot2=0;
memset(zi,0,sizeof zi);
memset(lin,0,sizeof lin);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&y,&x);
//x独自 y邻居
if(x>y){
zi[++tot1]=(node){x,y};
zizizi+=x;
}
else {
lin[++tot2]=(node){x,y};
ans+=y;
}
}
if(tot2==1){
ans=lin[1].a;
}
m-=tot2;
ll awa=m/2;
// cout<<m<<" "<<awa<<" "<<ans<<" "<<zizizi<<" "<<tot1<<" "<<tot2<<endl;
if(awa>=tot1) {
printf("%lld\n",ans+zizizi);
continue;
}else{
sort(zi+1,zi+tot1+1,cmp);
ll kkk=max(m-tot1,0ll);
ll jian=0;
// cout<<"kkk:"<<kkk<<" tot1:"<<tot1<<endl;
for(int i=1;i<=tot1-kkk;i++)jian+=zi[i].b-zi[i].a;
if(jian&&tot2==1) ans=lin[1].b;
printf("%lld\n",ans+zizizi+jian);
}
}
return 0;
}
//3
//4 5
//1 100
//100 1
//100 1
//100 1
//2 2
//1 10
//1 10
//2 3
//100 50
//1 1000
//1
//4 6
//1 10000
//1 1000
//1 100
//2 3
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 19276kb
input:
3 4 5 1 100 100 1 100 1 100 1 2 2 1 10 1 10 2 3 100 50 1 1000
output:
400 2 1050
result:
ok 3 number(s): "400 2 1050"
Test #2:
score: -100
Time Limit Exceeded
input:
100000 6 11 191141536 365120521 799679686 648574232 102602909 467685128 405440859 796808887 384858152 191995380 433392826 195648471 5 13 831367906 510447872 795639287 575551283 811207605 176441088 240156289 946977042 133416463 721098873 5 5 806744021 699586200 630510306 637827160 49223781 641709297 ...
output:
3247545200 4106290713 2653993029 5122532137 5570513606 2031887824 2044500908 1345295010 6815058419 2237593918 6646615756 5638337819 3690874076 5497726904 5513905900 5404435094 4705403467 2411992217 3430587752 5098767681 3921151709 1271949960 2692878616 3833748807 2409784919 850381192 6464787173 8839...