QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#141268#6525. New Housescy1999AC ✓435ms4836kbC++811b2023-08-17 10:06:042023-08-17 10:06:08

Judging History

This is the latest submission verdict.

  • [2023-08-17 10:06:08]
  • Judged
  • Verdict: AC
  • Time: 435ms
  • Memory: 4836kb
  • [2023-08-17 10:06:04]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const maxn = 5e5+10;
struct node{
	int a,b;
	
}p[maxn];

bool cmp(node x,node y){
	return (x.b - x.a) > (y.b - y.a);
}
signed main(){
	int t;
	cin >> t;
	while(t--){
		int n,m;
		cin >> n >> m ;
		int sum = 0;
		for(int i = 1;i <= n;i ++){
			cin >> p[i].a>>p[i].b;
			sum += p[i].a;
		}
		if(n==1){
			cout << p[1].b<<'\n';
			continue;
			
		}
		
	
		sort(p+1,p+n+1,cmp);
		int tmp = 0;
		int k = 0;
		for(int i = 1;i <= n&&i <= m - n;i ++){
			if(p[i].b - p[i].a <0)break;
			tmp = i;
			k += (p[i].b - p[i].a);
			
		}
		
		if(tmp!=n-1)cout << sum + k<<'\n';
        else {
        	cout << max(sum + k - (p[tmp].b - p[tmp].a),sum + k + (p[n].b - p[n].a))<<'\n';
        }		
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

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: 0
Accepted
time: 435ms
memory: 3408kb

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
1857678917
6815058419
2237593918
6646615756
5638337819
3690874076
5497726904
5513905900
5404435094
4705403467
2411992217
3430587752
5098767681
3921151709
1445672728
2692878616
3833748807
2716183054
974485573
6464787173
8839...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 374ms
memory: 3584kb

input:

100000
2 4
171910845 724506309
259963066 888690008
7 8
953968751 356200645
849910110 806488159
854691378 564448772
233557983 165114038
255658257 12385446
666173054 713885466
955831392 860299505
2 6
813205501 321494719
279407788 802865765
4 8
57425442 736850668
801303313 183904228
13820953 38797054
4...

output:

1613196317
4817503337
1124360484
2136575299
1409199188
3637650680
6262687872
988232227
3651377959
3865729450
967276858
5411226361
5602586585
4319610954
2833710199
4042904612
532626145
3528068938
2661203300
5355268131
284146202
5233667938
6490342667
2369703443
5973463590
5902979500
6331061629
4321393...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 237ms
memory: 3396kb

input:

100000
1 1
7 4
6 16
7 5
8 2
5 6
8 5
10 4
9 3
10 25
5 10
4 5
8 10
5 10
2 6
5 9
6 8
9 10
8 6
6 7
9 13
6 7
9 8
8 1
6 5
2 10
7 1
2 2
6 4
10 3
10 28
4 3
5 3
2 3
9 10
4 2
5 8
10 8
9 1
6 5
6 6
10 27
10 4
3 6
6 4
5 9
1 5
9 9
1 10
9 2
2 6
7 4
9 27
8 8
4 5
1 1
4 2
6 4
3 9
2 8
7 8
4 4
5 11
9 8
6 4
9 4
9 2
4 3
...

output:

4
48
82
65
65
77
53
37
28
67
59
37
37
59
14
64
7
18
69
38
42
38
49
31
54
40
37
6
6
64
34
10
49
44
14
32
4
50
35
43
43
61
56
79
6
66
68
32
15
48
59
10
41
64
52
14
48
14
47
33
62
52
9
14
41
67
10
37
26
6
46
19
34
24
63
25
49
37
66
44
2
11
34
29
23
13
26
46
41
26
24
18
2
11
55
38
3
31
4
24
25
63
47
3
7...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 124ms
memory: 4836kb

input:

10
92180 261153
4 1
6 4
1 1
2 4
6 1
3 3
6 3
1 8
7 4
7 4
4 5
8 6
3 4
6 2
8 10
4 2
6 1
5 4
10 3
6 4
8 1
10 4
3 6
9 3
10 7
10 3
3 8
1 6
10 9
4 1
7 9
3 9
9 5
6 8
7 4
1 2
6 8
10 8
4 5
6 8
2 6
8 10
2 1
5 4
9 5
8 5
4 7
5 8
6 2
5 3
4 4
9 7
9 2
4 5
10 7
2 10
5 3
4 10
3 2
9 7
3 9
7 6
10 6
8 4
7 5
3 10
2 2
2 2...

output:

658292
447048
594322
412878
350012
390453
659220
539463
407734
389596

result:

ok 10 numbers