QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#528602#2784. Aliensxyz123#4 11ms12272kbC++231.7kb2024-08-23 16:46:212024-08-23 16:46:21

Judging History

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

  • [2024-08-23 16:46:21]
  • 评测
  • 测评结果：4
  • 用时：11ms
  • 内存：12272kb
查看
  • [2024-08-23 16:46:21]
  • 提交

answer

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

long long dp[1000001],a,b,cn,g[1000001],f[1000001];
struct p{long long q,w;}l[1000001],m[1000001];
bool cmp(p qq,p ww){if(qq.q==ww.q) return qq.w>ww.w;return qq.q<ww.q;}
void ch(long long qq)
{
	dp[0]=0,g[0]=0;
	for(int i=1;i<=b;i++)
	{
		dp[i]=1e18,g[i]=0;
		for(int j=0;j<i;j++)
		{
			long long tt=dp[j]+(m[i].w+1-m[j+1].q)*(m[i].w+1-m[j+1].q)-f[j]+qq;
//			cout<<tt<<" "<<dp[j]<<" "<<f[j]<<"\n";
			if(tt<dp[i]) dp[i]=tt,g[i]=g[j]+1;
			else if(tt==dp[i]&&g[j]+1<g[i]) dp[i]=tt,g[i]=g[j]+1;
		}
	}
//	cout<<qq<<" "<<dp[b]<<" "<<g[b]<<"\n";
}
long long take_photos(int n, int mm, int k, std::vector<int> r, std::vector<int> c) {
	a=n,b=mm;
	swap(a,b);
	long long ll=0,rr=1e12;
	for(int i=0;i<b;i++)
	{
		if(r[i]<c[i]) l[i+1]=p{r[i]+1,c[i]+1};
		else l[i+1]=p{c[i]+1,r[i]+1};
	}
	sort(l+1,l+b+1,cmp);
	long long mxx=0;
	for(int i=1;i<=b;i++)
	{
//		cout<<l[i].q<<" "<<l[i].w<<"\n";
		if(cn>0&&m[cn].w>=l[i].w) continue;
		else m[++cn]=l[i];
	}b=cn;
	for(int i=1;i<b;i++)
	{
		if(m[i].w>=m[i+1].q) f[i]=(m[i].w-m[i+1].q+1)*(m[i].w-m[i+1].q+1);
	}
//	cout<<b<<"\n";
//	for(int i=1;i<=b;i++) cout<<m[i].q<<" "<<m[i].w<<"\n";
//	exit(0);
	long long ann=0;
	while(ll<=rr)
	{
		long long mid=((ll+rr)>>1);
		ch(mid);
		if(g[b]<=k) ann=mid,rr=mid-1;
		else ll=mid+1;
	}
	ch(ann);
    return dp[b]-g[b]*ann;
}

//int main() {
//    int n, m, k;
//    assert(3 == scanf("%d %d %d", &n, &m, &k));
//    std::vector<int> r(n), c(n);
//    for (int i = 0; i < n; i++) {
//        assert(2 == scanf("%d %d", &r[i], &c[i]));
//    }
//    long long ans = take_photos(n, m, k, r, c);
//    
//    
//    printf("%lld\n", ans);
//    return 0;
//}
源文件, 语言: C++23

詳細信息

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 0ms
memory: 10240kb

input:

2 6 2
1 4
4 1

output:

098d134608c94f7413faac591054ee35
16

result:

ok Correct answer: answer = 16

Test #2:

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

input:

1 2 1
0 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #3:

score: 4
Accepted
time: 0ms
memory: 10016kb

input:

2 2 2
0 0
1 0

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #4:

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

input:

2 3 2
0 1
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #5:

score: 4
Accepted
time: 2ms
memory: 12020kb

input:

4 4 4
1 3
0 1
2 1
2 2

output:

098d134608c94f7413faac591054ee35
12

result:

ok Correct answer: answer = 12

Test #6:

score: 4
Accepted
time: 0ms
memory: 11992kb

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: 4
Accepted
time: 0ms
memory: 12272kb

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: 4
Accepted
time: 1ms
memory: 11984kb

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: 4
Accepted
time: 1ms
memory: 11988kb

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: 4
Accepted
time: 0ms
memory: 9936kb

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: 4
Accepted
time: 2ms
memory: 12020kb

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: 4
Accepted
time: 0ms
memory: 11984kb

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: 4
Accepted
time: 1ms
memory: 10224kb

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: 4
Accepted
time: 0ms
memory: 11956kb

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: 4
Accepted
time: 2ms
memory: 12020kb

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: 4
Accepted
time: 2ms
memory: 11980kb

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: 4
Accepted
time: 1ms
memory: 12004kb

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: 4
Accepted
time: 1ms
memory: 9900kb

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: 4
Accepted
time: 1ms
memory: 9928kb

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: 4
Accepted
time: 0ms
memory: 12044kb

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: 4
Accepted
time: 1ms
memory: 9936kb

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: 4
Accepted
time: 1ms
memory: 9944kb

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: 9932kb

input:

2 2 1
0 0
1 1

output:

098d134608c94f7413faac591054ee35
4

result:

ok Correct answer: answer = 4

Test #24:

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

input:

4 3 2
0 0
0 0
0 0
0 0

output:

098d134608c94f7413faac591054ee35
1

result:

ok Correct answer: answer = 1

Test #25:

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

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: 12
Accepted
time: 1ms
memory: 9952kb

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: 12
Accepted
time: 1ms
memory: 9940kb

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

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
77137

result:

ok Correct answer: answer = 77137

Test #29:

score: 0
Wrong Answer
time: 5ms
memory: 10248kb

input:

500 1000 250
599 599
14 14
176 176
963 963
93 93
257 257
403 403
741 741
854 854
862 862
778 778
489 489
711 711
623 623
163 163
750 750
649 649
441 441
245 245
311 311
429 429
756 756
572 572
766 766
837 837
137 137
719 719
244 244
519 519
287 287
251 251
818 818
789 789
305 305
400 400
262 262
359...

output:

098d134608c94f7413faac591054ee35
925

result:

wrong answer Wrong answer: output = 925, expected = 764

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
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #112:

score: 19
Accepted
time: 11ms
memory: 12088kb

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
999889968863

result:

ok Correct answer: answer = 999889968863

Test #113:

score: 19
Accepted
time: 7ms
memory: 12172kb

input:

50000 1000000 8
399073 559474
284146 99898
375389 122686
80775 357801
319456 379430
251948 425589
470164 726942
180115 677331
174879 609886
879336 274639
172132 755286
73776 907221
655053 808794
127586 558652
158465 298754
474407 208895
819275 192292
754904 362313
942856 453040
205348 662961
554428 ...

output:

098d134608c94f7413faac591054ee35
999861384931

result:

ok Correct answer: answer = 999861384931

Test #114:

score: 19
Accepted
time: 7ms
memory: 12172kb

input:

50000 1000000 49
395775 225827
107876 226736
693613 305582
901641 53447
504609 994262
5047 608677
484540 120957
36722 397124
825085 736548
553505 750564
978962 460112
450110 15095
336393 250376
517875 417904
995371 271663
905045 858978
240324 844363
468528 106252
331737 99932
78429 675647
897302 755...

output:

098d134608c94f7413faac591054ee35
999811809929

result:

ok Correct answer: answer = 999811809929

Test #115:

score: 19
Accepted
time: 7ms
memory: 12080kb

input:

50000 1000000 99
595092 535757
193430 467573
548323 750849
89122 500291
562841 861078
924882 20121
116634 939464
735914 577485
455078 104026
434181 806496
208311 437995
721445 878386
306688 927173
567734 38513
58134 237797
539935 425782
797486 99058
692233 731520
455780 628428
543934 291599
230276 6...

output:

098d134608c94f7413faac591054ee35
999869756441

result:

ok Correct answer: answer = 999869756441

Test #116:

score: 0
Time Limit Exceeded

input:

50000 60000 2
8597 8597
9329 9329
9757 9757
52906 52906
3767 3767
1550 1550
27747 27747
32959 32959
51190 51190
11613 11613
5014 5014
2527 2527
14847 14847
23167 23167
35500 35500
53108 53108
37110 37110
56602 56602
39663 39663
4674 4674
37075 37075
7077 7077
24718 24718
17596 17596
8332 8332
15727 ...

output:

Unauthorized output

result:

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%
English 繁體中文 简体中文

伺服器時間: 2024-11-30 02:35:33 | 開源專案