QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384495 | #6532. Trading | DDT | TL | 1ms | 4456kb | C++23 | 870b | 2024-04-10 00:36:51 | 2024-04-10 00:36:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
#define endl '\n'
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> PII;
void solve()
{
PII a[100010];
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
cnt+=a[i].y;
}
sort(a+1,a+n+1);
int cnt1,cnt2;
if(cnt&1)cnt1=(cnt-1)/2;
else cnt1=cnt/=2;
cnt2=cnt1;
int cb=0,xs=0;
for(int i=1;i<=n;i++)
{
cb+=a[i].x*min(a[i].y,cnt1);
cnt1-=min(a[i].y,cnt1);
if(cnt1<=0)break;
}
for(int i=n;i>=1;i--)
{
xs+=a[i].x*min(a[i].y,cnt2);
cnt2-=min(a[i].y,cnt2);
if(cnt2<=0)break;
}
cout<<xs-cb<<endl;
}
/*
10 2
20 4
25
30 7
50 1
*/
int main()
{
ios::sync_with_stdio(false);
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4456kb
input:
2 4 10 2 30 7 20 4 50 1 2 1 100 1 1000
output:
100 0
result:
ok 2 number(s): "100 0"
Test #2:
score: -100
Time Limit Exceeded
input:
100000 8 567091 283679 875020 918237 314684 148083 456411 304598 766056 882388 135371 326501 578773 250140 221306 874117 5 126777 129517 846433 679825 649281 330021 427768 362636 390068 692169 5 657677 231119 941936 991342 901241 15133 660372 970476 698958 209343 10 478657 163635 752788 819629 82110...
output:
-744919867 1894303037 -1134720638 -1210578816 -1601339592 -96866416 1385928560 -355998120 1372696906 1149443172 161170200 2008824615 -390796220 1518618424 0 -22761517 -2039532899 2019743226 -448976944 1846443908 1102275380 -1547135780 -774885684 0 726882555 1743132609 1629150693 -1888470433 75192932...