QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150653#2784. AliensHe_Ren4 9ms4316kbC++171.2kb2023-08-25 23:05:062023-08-25 23:05:08

Judging History

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

  • [2023-08-25 23:05:08]
  • 评测
  • 测评结果：4
  • 用时：9ms
  • 内存：4316kb
查看
  • [2023-08-25 23:05:06]
  • 提交

answer

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

ll calc(ll x,ll y)
{
	return (y-x+1) * (y-x+1);
}
ll calc(array<int,2> t)
{
	return calc(t[0], t[1]);
}

array<int,2> p[MAXN];

ll take_photos(int n, int, int d, vector<int> _r, vector<int> _c)
{
	for(int i=1; i<=n; ++i)
	{
		int x = _r[i-1], y = _c[i-1];
		if(x > y) swap(x, y);
		p[i] = {x, y};
	}
	
	sort(p+1, p+n+1);
	int nn = 0;
	for(int i=1; i<=n; ++i)
	{
		if(nn == 0 || p[i][1] > p[nn][1])
			p[++nn] = p[i];
	}
	n = nn;
	
	ll ans = 0;
	for(int i=1; i<=n; ++i)
		ans += calc(p[i]);
	
	for(int i=1; i<n; ++i)
		if(p[i+1][0] <= p[i][1])
			ans -= calc(p[i+1][0], p[i][1]);
	
	while(n > d)
	{
		int mn = 1;
		ll mnval = linf;
		for(int i=1; i<n; ++i)
		{
			ll cur = calc(p[i][0], p[i+1][1]) - calc(p[i]) - calc(p[i+1]);
			if(p[i+1][0] <= p[i][1])
				cur -= calc(p[i+1][0], p[i][1]);	
			
			if(cur < mnval)
				mn = i, mnval = cur;
		}
		ans += mnval;
		
		p[mn][1] = p[mn+1][1];
		for(int i=mn+1; i<n; ++i)
			p[i] = p[i+1];
		--n;
	}
	
	return ans;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 1ms
memory: 3712kb

input:

2 6 2
1 4
4 1

output:

098d134608c94f7413faac591054ee35
16

result:

ok Correct answer: answer = 16

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

1 2 1
0 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #3:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

2 2 2
0 0
1 0

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #4:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

2 3 2
0 1
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #5:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

4 4 4
1 3
0 1
2 1
2 2

output:

098d134608c94f7413faac591054ee35
12

result:

ok Correct answer: answer = 12

Test #6:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

5 8 5
0 5
2 6
7 4
4 5
2 6

output:

098d134608c94f7413faac591054ee35
52

result:

ok Correct answer: answer = 52

Test #7:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

8 20 8
6 14
5 13
1 8
17 15
6 9
1 9
2 0
17 8

output:

098d134608c94f7413faac591054ee35
210

result:

ok Correct answer: answer = 210

Test #8:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

10 10 10
2 2
3 6
8 6
8 3
6 9
4 0
8 4
8 1
0 8
8 9

output:

098d134608c94f7413faac591054ee35
88

result:

ok Correct answer: answer = 88

Test #9:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

10 100 10
98 25
55 31
36 25
38 77
9 82
11 69
88 42
47 49
19 91
61 13

output:

098d134608c94f7413faac591054ee35
7696

result:

ok Correct answer: answer = 7696

Test #10:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

50 1 50
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #11:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

50 50 50
25 25
44 12
46 47
4 26
10 35
10 3
13 27
14 16
6 28
10 0
27 46
2 19
10 36
29 49
13 16
6 38
32 48
33 33
47 45
8 13
5 21
14 25
21 41
47 49
26 7
4 7
5 34
5 24
16 24
18 26
29 10
32 39
14 39
35 32
11 1
49 17
24 18
38 14
32 48
46 1
45 46
17 36
29 31
24 48
12 33
4 44
38 32
11 6
25 47
9 49

output:

098d134608c94f7413faac591054ee35
2374

result:

ok Correct answer: answer = 2374

Test #12:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

50 100 50
0 20
49 26
21 27
10 67
79 9
38 75
39 27
36 51
75 81
70 37
57 74
57 64
13 76
53 95
25 11
62 37
78 38
39 19
46 7
92 71
40 27
73 11
30 55
60 67
79 48
3 69
1 27
41 54
80 40
50 50
9 49
75 11
90 62
2 71
14 40
30 48
3 53
68 24
99 25
8 49
35 80
31 24
21 11
92 9
4 97
45 61
56 83
68 75
35 84
77 20

output:

098d134608c94f7413faac591054ee35
9502

result:

ok Correct answer: answer = 9502

Test #13:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

49 7 49
5 3
0 6
6 2
3 3
4 2
3 4
0 3
1 3
2 4
5 1
1 0
2 1
3 0
4 4
1 6
0 5
1 4
6 3
6 6
6 5
4 0
3 5
5 5
2 0
4 5
3 2
0 2
1 5
2 5
6 4
1 1
5 0
0 4
6 0
5 4
2 6
0 1
5 2
4 6
5 6
3 1
3 6
0 0
4 3
1 2
2 2
4 1
2 3
6 1

output:

098d134608c94f7413faac591054ee35
49

result:

ok Correct answer: answer = 49

Test #14:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

50 51 50
38 39
6 7
44 45
24 25
30 31
25 26
49 50
10 11
18 19
36 37
7 8
15 16
21 22
32 33
13 14
5 6
11 12
45 46
48 49
47 48
28 29
26 27
40 41
14 15
33 34
23 24
2 3
12 13
19 20
46 47
8 9
35 36
4 5
42 43
39 40
20 21
1 2
37 38
34 35
41 42
22 23
27 28
0 1
31 32
9 10
16 17
29 30
17 18
43 44
3 4

output:

098d134608c94f7413faac591054ee35
151

result:

ok Correct answer: answer = 151

Test #15:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

50 100 50
38 88
6 56
44 94
24 74
30 80
25 75
49 99
10 60
18 68
36 86
7 57
15 65
21 71
32 82
13 63
5 55
11 61
45 95
48 98
47 97
28 78
26 76
40 90
14 64
33 83
23 73
2 52
12 62
19 69
46 96
8 58
35 85
4 54
42 92
39 89
20 70
1 51
37 87
34 84
41 91
22 72
27 77
0 50
31 81
9 59
16 66
29 79
17 67
43 93
3 53

output:

098d134608c94f7413faac591054ee35
7550

result:

ok Correct answer: answer = 7550

Test #16:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

50 100 50
37 79
7 50
40 90
24 69
27 75
25 70
46 99
9 54
19 62
35 78
8 51
11 60
21 67
30 75
11 57
4 50
10 55
40 92
45 97
41 95
27 73
25 71
38 80
11 57
30 75
24 68
2 49
11 56
20 64
40 92
9 53
35 77
3 49
39 83
37 80
20 67
1 48
36 79
31 76
38 81
21 68
26 71
0 48
27 75
9 53
13 61
27 74
14 62
39 84
3 49

output:

098d134608c94f7413faac591054ee35
7220

result:

ok Correct answer: answer = 7220

Test #17:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

50 100 50
49 99
48 98
47 97
46 96
45 95
44 94
43 93
42 92
41 91
40 90
39 89
38 88
37 87
36 86
35 85
34 84
33 83
32 82
31 81
30 80
29 79
28 78
27 77
26 76
25 75
24 74
23 73
22 72
21 71
20 70
19 69
18 68
17 67
16 66
15 65
14 64
13 63
12 62
11 61
10 60
9 59
8 58
7 57
6 56
5 55
4 54
3 53
2 52
1 51
0 50

output:

098d134608c94f7413faac591054ee35
7550

result:

ok Correct answer: answer = 7550

Test #18:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

50 100 50
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #19:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

50 100 50
0 99
1 98
3 98
3 96
3 96
4 93
4 92
5 92
6 91
8 91
9 91
10 90
11 90
12 85
12 82
17 82
19 82
19 81
20 80
21 76
21 76
22 75
22 75
23 73
23 72
24 72
24 71
25 71
25 70
28 68
28 66
29 66
30 64
31 63
31 63
33 62
34 61
36 60
37 60
39 60
40 59
43 59
44 59
45 58
45 57
46 56
47 55
50 53
50 52
51 52

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #20:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

50 100 50
61 62
12 15
81 81
49 50
78 85
62 69
55 61
57 57
22 25
77 78
2 5
8 12
62 67
49 50
19 25
60 62
71 77
74 74
90 95
33 34
24 26
47 54
45 51
72 75
89 89
18 19
36 38
6 8
1 3
25 26
73 77
35 38
1 4
55 57
85 91
82 86
66 66
18 18
3 5
61 64
32 32
21 22
61 63
79 83
74 80
68 74
72 75
75 81
66 69
51 55

output:

098d134608c94f7413faac591054ee35
624

result:

ok Correct answer: answer = 624

Test #21:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

50 100 50
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99
0 99

output:

098d134608c94f7413faac591054ee35
10000

result:

ok Correct answer: answer = 10000

Test #22:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

1 1 1
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 12
Accepted
time: 1ms
memory: 3684kb

input:

2 2 1
0 0
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #24:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

4 3 2
0 0
0 0
0 0
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #25:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

5 5 2
2 2
3 3
4 4
3 3
3 3

output:

098d134608c94f7413faac591054ee35
5

result:

ok Correct answer: answer = 5

Test #26:

score: 0
Accepted
time: 1ms
memory: 3740kb

input:

10 20 3
3 3
15 15
10 10
18 18
4 4
7 7
15 15
2 2
10 10
7 7

output:

098d134608c94f7413faac591054ee35
41

result:

ok Correct answer: answer = 41

Test #27:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

20 1000 5
737 737
714 714
662 662
163 163
683 683
615 615
23 23
246 246
724 724
90 90
802 802
557 557
146 146
429 429
816 816
164 164
638 638
568 568
957 957
904 904

output:

098d134608c94f7413faac591054ee35
71923

result:

ok Correct answer: answer = 71923

Test #28:

score: -12
Wrong Answer
time: 1ms
memory: 3660kb

input:

200 1000 10
69 69
277 277
350 350
753 753
741 741
849 849
993 993
95 95
928 928
789 789
333 333
795 795
493 493
253 253
661 661
780 780
17 17
394 394
487 487
719 719
426 426
297 297
885 885
323 323
981 981
916 916
0 0
997 997
757 757
374 374
467 467
787 787
297 297
216 216
599 599
62 62
936 936
777 ...

output:

098d134608c94f7413faac591054ee35
80476

result:

wrong answer Wrong answer: output = 80476, expected = 77137

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #112:

score: 0
Wrong Answer
time: 9ms
memory: 4316kb

input:

50000 1000000 3
360946 187012
56354 290116
389944 194589
327798 454716
248464 891509
615396 878303
736802 689759
446833 816714
552228 948958
34870 257015
911026 191884
761150 821028
341778 82756
125288 719663
86132 290045
145161 627383
25381 217026
756213 671192
686079 478553
648300 785174
706912 93...

output:

098d134608c94f7413faac591054ee35
-7846120480605

result:

wrong answer Wrong answer: output = -7846120480605, expected = 999889968863

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-30 02:51:41 | 开源项目