QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#384495#6532. TradingDDTTL 1ms4456kbC++23870b2024-04-10 00:36:512024-04-10 00:36:51

Judging History

你现在查看的是最新测评结果

  • [2024-04-10 00:36:51]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4456kb
  • [2024-04-10 00:36:51]
  • 提交

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...

result: