QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#643001#360. CultivationSimonLJK30 9ms6084kbC++173.2kb2024-10-15 17:44:472024-10-15 17:44:48

Judging History

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

  • [2024-10-15 17:44:48]
  • 评测
  • 测评结果：30
  • 用时：9ms
  • 内存：6084kb
查看
  • [2024-10-15 17:44:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp(a,b) make_pair(a,b)
const int N=309;
const int inf=2e9+10;
int r,c,n,ans;
struct node{
	int x,y;
	bool operator <(const node&A)const{
		return x<A.x;
	}
}p[N];
int L[N][N],R[N][N],Len[N][N];
multiset<int> ms;
multiset<int> ::iterator it,it1,it2;
void init(){
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++) ms.insert(p[j].y);
		L[i][n]=(*ms.begin())-1;
		it=ms.end(); it--; R[i][n]=c-(*it);
		it1=ms.begin(); it2=ms.begin(); it2++;
		for(;it2!=ms.end();it1++,it2++)
			Len[i][n]=max(Len[i][n],(*it2)-(*it1)-1);
		for(int j=n;j>i;j--){
			Len[i][j-1]=Len[i][j];
			it=ms.find(p[j].y);
			if(it!=ms.begin()){
				it--; it1=it;
				it++; it++; it2=it;
				if(it2!=ms.end())
					Len[i][j-1]=max(Len[i][j-1],(*it2)-(*it1)-1);
			}
			ms.erase(ms.find(p[j].y));
			it=ms.begin(); L[i][j-1]=(*it)-1;
			it=ms.end(); it--; R[i][j-1]=c-(*it);
			Len[i][j-1]=max(Len[i][j-1],L[i][j-1]+R[i][j-1]);
		}
		ms.clear();
	}
	return;
}
int solve(int len){//鎷撳睍len,闀垮害len+1
	list<pair<int,int> > ql,qr,qlen;
	ql.push_back(mp(inf,0)); qr.push_back(mp(inf,0)); qlen.push_back(mp(inf,0));
	int res=r+c;
	int pi=0,po=0;
	int ln=1,rn=0,nxt,now;
	p[n+1]=(node){inf,inf};
	while(pi<n||po<n){
		nxt=min(p[pi+1].x,p[po+1].x+len+1/*outside*/);
		while(pi<n&&p[pi+1].x==nxt){ rn++; pi++; }
		while(po<n&&p[po+1].x+len+1==nxt){ ln++; po++; }
		now=nxt; nxt=min(p[pi+1].x,p[po+1].x+len+1/*outside*/);
		if(pi==n&&po==n) break;
		nxt--;
		while(!ql.empty()&&ql.back().first<=L[ln][rn]) ql.pop_back();
		ql.push_back(mp(L[ln][rn],nxt));
		while(!qr.empty()&&qr.back().first<=R[ln][rn]) qr.pop_back();
		qr.push_back(mp(R[ln][rn],nxt));
		while(!qlen.empty()&&qlen.back().first<=Len[ln][rn]) qlen.pop_back();
		qlen.push_back(mp(Len[ln][rn],nxt));
		if(nxt>=r+p[1].x-1){
			while(ql.front().second<=nxt-r) ql.pop_front();
			while(qr.front().second<=nxt-r) qr.pop_front();
			while(qlen.front().second<=nxt-r) qlen.pop_front();
			res=min(res,max(ql.front().first+qr.front().first,qlen.front().first));
		}
	}
	return res;
}
vector<int> vx,vec;
signed main(){
//	freopen("cheat5.in","r",stdin);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>r>>c>>n; ans=r+c-2;
	for(int i=1;i<=n;i++){
		cin>>p[i].x>>p[i].y;
		vx.push_back(p[i].x);
	}
	sort(p+1,p+n+1);
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	int l=vx[0]-1,rr=r-vx.back(); int mx=l+rr;
	for(int i=1;i<vx.size();i++) mx=max(mx,vx[i]-vx[i-1]-1);
	vec.push_back(mx);
	for(int i=0;i<vx.size();i++)
		for(int j=i+1;j<vx.size();j++)
			vec.push_back(vx[j]-vx[i]),vec.push_back(vx[j]-vx[i]+1),vec.push_back(r-vx[j]+vx[i]-1),vec.push_back(r-vx[j]+vx[i]),vec.push_back(r+vx[j]-vx[i]-1),vec.push_back(r+vx[j]-vx[i]);
	for(int i=0;i<vx.size();i++)
		vec.push_back(vx[i]-1),vec.push_back(r-vx[i]);
	sort(vec.begin(),vec.end());
	for(int i=0;i<vec.size();i++) if(vec[i]<mx) vec[i]=mx;
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	init();
//	if(c==1000000000){
//		cout<<Len[1][n]<<endl;
//		return 0;
//	}
	for(int len:vec)
//	for(int len=mx;len<=r;len++)
		ans=min(ans,solve(len)+len);
	cout<<ans;
	return 0;
}
源文件, 语言: C++17

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 5684kb

input:

2 4
2
1 1
1 4

output:

3

result:

ok single line: '3'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3576kb

input:

4 1
1
2 1

output:

3

result:

ok single line: '3'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3828kb

input:

3 3
3
1 2
1 3
3 3

output:

3

result:

ok single line: '3'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3748kb

input:

2 2
1
1 2

output:

2

result:

ok single line: '2'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3884kb

input:

4 4
10
4 2
2 3
2 4
4 1
1 2
2 1
4 3
3 3
3 1
1 4

output:

2

result:

ok single line: '2'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

4 4
1
4 1

output:

6

result:

ok single line: '6'

Test #7:

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

input:

4 4
3
2 2
3 3
1 4

output:

5

result:

ok single line: '5'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3700kb

input:

4 4
15
4 3
2 4
4 4
4 1
3 3
1 2
3 1
2 1
3 4
3 2
4 2
2 3
1 3
2 2
1 4

output:

1

result:

ok single line: '1'

Test #9:

score: 5
Accepted
time: 0ms
memory: 5624kb

input:

4 3
3
2 1
2 3
4 1

output:

3

result:

ok single line: '3'

Test #10:

score: 5
Accepted
time: 1ms
memory: 5612kb

input:

4 4
2
3 4
2 4

output:

5

result:

ok single line: '5'

Test #11:

score: 5
Accepted
time: 0ms
memory: 3572kb

input:

2 4
1
1 2

output:

4

result:

ok single line: '4'

Test #12:

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

input:

3 3
4
2 1
1 1
3 2
3 1

output:

2

result:

ok single line: '2'

Test #13:

score: 5
Accepted
time: 0ms
memory: 3836kb

input:

3 4
3
1 4
3 3
3 4

output:

4

result:

ok single line: '4'

Test #14:

score: 5
Accepted
time: 0ms
memory: 5624kb

input:

3 3
2
2 1
3 3

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4 4
2
2 4
3 1

output:

6

result:

ok single line: '6'

Test #16:

score: 5
Accepted
time: 0ms
memory: 3832kb

input:

4 4
3
2 2
2 1
4 2

output:

4

result:

ok single line: '4'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 10
Accepted
time: 1ms
memory: 3628kb

input:

15 15
20
6 13
14 4
11 13
15 3
12 4
10 4
11 6
8 9
12 12
2 15
4 3
8 15
8 4
3 1
5 10
11 12
8 7
13 10
11 4
1 3

output:

13

result:

ok single line: '13'

Test #18:

score: 10
Accepted
time: 0ms
memory: 3988kb

input:

25 25
66
24 6
12 18
11 2
24 18
6 9
20 6
15 19
17 2
15 9
15 20
18 9
5 19
9 2
6 12
22 16
6 2
1 5
14 24
12 21
17 24
10 15
21 1
20 22
11 24
11 4
6 21
18 12
25 20
16 3
18 16
6 4
20 9
6 15
24 14
3 20
9 9
25 9
18 6
4 16
12 7
14 22
20 25
24 10
11 14
17 6
23 23
21 12
18 22
8 23
1 11
17 18
8 5
3 7
1 17
8 12
4...

output:

9

result:

ok single line: '9'

Test #19:

score: 10
Accepted
time: 0ms
memory: 4012kb

input:

36 38
28
30 5
4 23
29 20
1 36
8 28
8 9
5 26
23 16
26 1
24 38
22 36
4 26
9 7
10 24
20 11
31 5
24 30
26 30
18 15
14 1
23 31
20 7
23 30
33 9
27 33
8 7
9 16
33 5

output:

30

result:

ok single line: '30'

Test #20:

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

input:

10 40
19
7 5
8 38
4 7
8 5
4 30
1 33
1 16
2 21
8 33
4 36
6 20
6 27
4 14
10 15
9 30
8 13
4 15
10 9
5 22

output:

17

result:

ok single line: '17'

Test #21:

score: 10
Accepted
time: 1ms
memory: 3952kb

input:

40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14

output:

50

result:

ok single line: '50'

Test #22:

score: 10
Accepted
time: 2ms
memory: 5720kb

input:

40 40
120
23 22
31 36
2 4
2 32
14 40
23 32
18 11
27 36
7 1
25 33
22 40
34 9
26 20
18 7
35 7
3 17
19 6
5 27
19 30
33 15
2 15
19 15
4 8
27 1
8 27
10 2
11 39
31 27
32 35
17 4
18 22
2 7
7 10
5 14
40 23
3 36
6 6
6 15
21 35
27 39
25 1
40 11
36 16
8 23
35 27
18 21
24 39
13 22
4 3
12 17
31 16
3 6
6 4
3 30
2...

output:

16

result:

ok single line: '16'

Test #23:

score: 10
Accepted
time: 1ms
memory: 3812kb

input:

40 40
33
10 22
10 3
7 11
12 14
11 12
1 21
6 23
3 11
8 24
3 40
8 14
7 25
8 15
12 3
10 7
4 32
7 32
9 32
9 30
4 22
8 22
11 24
6 19
10 16
10 2
9 4
10 15
9 28
7 1
4 31
7 35
4 18
2 35

output:

46

result:

ok single line: '46'

Test #24:

score: 10
Accepted
time: 4ms
memory: 5120kb

input:

40 40
200
10 16
27 15
18 11
16 25
34 7
39 25
26 15
12 20
8 1
20 14
25 27
33 4
29 40
20 33
8 9
32 16
37 25
34 27
31 23
30 8
40 30
35 37
27 7
18 27
36 30
13 30
12 32
32 4
15 21
29 39
4 32
8 7
12 21
35 40
32 29
34 17
22 30
12 34
34 39
23 16
27 16
13 26
28 32
8 31
30 16
13 25
28 13
19 35
38 35
2 40
7 1
...

output:

14

result:

ok single line: '14'

Test #25:

score: 10
Accepted
time: 3ms
memory: 4760kb

input:

40 40
150
8 38
27 32
34 14
29 32
16 36
29 19
40 30
30 22
34 12
4 30
24 37
14 8
31 21
40 17
38 25
16 5
29 5
38 29
28 10
2 5
5 16
20 11
38 6
21 11
5 8
26 13
21 35
27 27
10 11
18 30
30 40
8 18
31 5
16 7
3 1
35 36
40 26
18 39
25 8
19 16
17 26
6 20
13 30
34 4
35 8
33 4
25 29
39 7
22 40
10 36
26 3
30 14
1...

output:

16

result:

ok single line: '16'

Test #26:

score: 10
Accepted
time: 9ms
memory: 5824kb

input:

40 40
300
5 29
4 30
10 5
19 1
11 37
8 26
2 12
29 25
13 33
4 36
15 9
6 39
27 35
34 14
35 27
32 26
14 35
23 35
23 34
12 6
2 21
20 29
20 23
5 21
15 11
7 13
6 23
33 7
19 22
20 31
28 25
7 18
15 39
25 1
2 16
5 23
5 28
7 21
5 31
8 29
16 14
18 29
16 3
3 23
20 35
24 34
14 4
14 30
39 18
25 5
19 37
28 10
7 11
...

output:

18

result:

ok single line: '18'

Test #27:

score: 10
Accepted
time: 8ms
memory: 5820kb

input:

40 40
300
23 5
15 1
34 20
36 22
19 4
31 19
11 34
13 33
3 20
18 4
27 10
37 21
14 11
30 34
8 29
6 26
32 33
8 10
1 14
40 40
4 22
19 31
6 28
37 16
22 34
38 17
16 2
18 36
12 4
38 15
1 24
1 18
32 8
6 18
35 26
12 36
25 2
38 20
19 3
25 12
2 34
35 22
10 36
26 3
10 22
36 8
29 33
3 39
5 10
7 9
36 14
24 5
5 21
...

output:

14

result:

ok single line: '14'

Test #28:

score: 10
Accepted
time: 4ms
memory: 5192kb

input:

39 40
200
9 40
2 33
16 32
14 33
14 27
3 28
5 31
36 30
15 22
23 17
22 28
13 10
4 14
24 35
4 35
12 22
28 32
8 37
7 31
1 37
28 21
39 22
12 17
7 20
35 16
10 12
12 6
27 31
33 15
19 16
13 35
26 35
10 19
15 25
18 19
21 9
11 9
39 4
3 31
20 24
37 26
22 38
13 40
18 12
29 4
31 2
10 26
2 39
2 3
18 9
14 34
39 23...

output:

15

result:

ok single line: '15'

Test #29:

score: 10
Accepted
time: 8ms
memory: 5856kb

input:

38 38
300
30 33
11 38
6 10
19 20
29 30
1 18
30 20
11 19
23 15
32 3
32 30
5 34
7 30
34 1
5 4
20 35
8 13
25 32
12 2
6 3
1 19
38 7
35 16
14 9
37 2
10 4
13 21
37 17
34 4
20 20
14 12
20 13
36 3
10 33
5 8
23 23
9 22
17 19
13 9
20 14
31 4
11 23
17 32
12 10
21 23
31 11
17 35
12 17
31 27
3 6
10 37
2 38
5 15
...

output:

9

result:

ok single line: '9'

Test #30:

score: 10
Accepted
time: 8ms
memory: 5888kb

input:

40 40
300
25 27
25 10
20 19
16 40
29 29
39 20
3 4
6 20
20 6
1 25
39 32
28 26
27 17
30 38
4 33
27 24
21 4
36 32
29 7
4 23
39 2
40 6
14 40
33 39
23 32
23 34
18 6
36 28
40 4
15 28
13 33
34 3
4 35
20 29
38 36
7 24
5 25
20 3
37 13
40 26
5 9
40 36
24 26
16 14
8 28
37 6
24 16
7 3
28 28
34 13
34 36
29 12
13...

output:

10

result:

ok single line: '10'

Test #31:

score: 10
Accepted
time: 9ms
memory: 5916kb

input:

40 40
300
31 12
30 38
21 17
11 12
1 28
10 37
10 13
5 22
18 21
28 37
23 40
29 32
21 33
5 3
21 24
14 15
2 23
9 33
15 31
38 12
37 8
37 26
1 5
28 34
22 10
18 29
30 39
23 34
25 37
35 1
10 7
25 11
10 38
34 30
18 1
12 1
10 25
16 11
35 40
26 30
5 15
23 3
22 22
16 4
8 21
12 23
24 29
4 27
40 5
18 15
35 38
1 1...

output:

9

result:

ok single line: '9'

Test #32:

score: 10
Accepted
time: 8ms
memory: 5828kb

input:

40 40
300
24 6
26 15
30 7
10 12
17 17
7 25
36 26
19 39
32 10
20 1
16 1
34 1
23 19
10 38
40 7
13 39
25 27
28 25
39 18
25 20
17 3
32 28
10 4
6 3
12 16
29 35
13 12
29 16
2 35
6 15
19 7
1 32
18 24
13 18
1 31
28 31
29 12
19 4
20 10
1 3
6 38
1 10
27 14
33 26
1 12
8 31
9 39
22 21
8 39
37 3
26 33
25 10
32 4...

output:

11

result:

ok single line: '11'

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #33:

score: 15
Accepted
time: 8ms
memory: 6016kb

input:

2 200000000
300
1 88265857
1 174408185
1 105379902
1 185252998
2 30206021
2 102367431
2 89739523
1 116153736
2 68837704
1 110817136
2 26646126
2 86276690
1 127329134
2 126441765
1 19927577
1 38738747
1 105161585
1 60367988
2 67085969
1 1865971
1 27164731
1 77127255
2 168438218
1 4482768
1 197852914
...

output:

3425851

result:

ok single line: '3425851'

Test #34:

score: 15
Accepted
time: 6ms
memory: 5864kb

input:

40 1000000000
300
20 483437001
11 245274001
5 80864001
2 7139001
36 895164001
32 773938001
27 666531001
36 894646001
20 467811001
36 877372001
4 76683001
25 599539001
25 604099001
34 834882001
6 105503001
12 279215001
27 655684001
16 364895001
19 439732001
4 61698001
39 973882001
38 925548001
28 684...

output:

19162076

result:

ok single line: '19162076'

Test #35:

score: 15
Accepted
time: 9ms
memory: 5832kb

input:

40 1000000000
300
38 393750001
12 93750001
33 31250002
18 68749999
36 631250003
14 581250003
37 843750003
39 31250001
17 6250002
11 481250000
3 818750001
37 568750002
20 281250001
36 731249999
3 731250003
30 206250000
14 893750002
18 618749999
2 868750003
9 243750003
9 781250000
39 168749999
37 8687...

output:

12500068

result:

ok single line: '12500068'

Test #36:

score: 15
Accepted
time: 9ms
memory: 6080kb

input:

40 1000000000
300
20 273611973
30 962515424
19 457562756
14 228419368
9 839242624
34 416448186
6 49326057
27 373662328
18 43718671
40 180109032
35 703858821
6 62818768
23 176704786
30 419420243
29 966647309
30 971207395
9 471992569
17 18782375
28 524707582
15 887562815
20 339788418
40 188122260
33 1...

output:

25840886

result:

ok single line: '25840886'

Test #37:

score: 15
Accepted
time: 8ms
memory: 5736kb

input:

35 1000000000
300
26 304985784
31 53820856
34 188129610
32 933853739
29 435634084
16 233290946
24 581180249
14 763935773
10 265931834
9 274498426
16 675425485
15 87227536
21 985415295
14 272012946
12 765102757
24 458857877
20 610373170
25 928877042
32 589674594
23 467914943
31 693779625
19 197133223...

output:

14686151

result:

ok single line: '14686151'

Test #38:

score: 15
Accepted
time: 8ms
memory: 6084kb

input:

40 1000000000
300
6 786763464
27 418721225
37 714875337
10 156646263
9 190541536
30 429336661
7 865464196
28 815774814
35 25779712
30 681279351
11 395942851
13 574687654
29 137106802
33 754832787
37 294845778
19 815900516
14 704212093
36 198711902
17 533523161
34 748841831
17 981957453
30 294955278
...

output:

21233330

result:

ok single line: '21233330'

Test #39:

score: 15
Accepted
time: 9ms
memory: 5884kb

input:

40 1000000000
300
40 70731728
31 860477266
8 270731733
14 56097551
5 524390251
21 148780485
6 60975598
26 612195132
13 997560998
36 426829256
32 7317081
1 256097581
25 457312359
12 241463431
5 85365829
18 4440737
1 436585368
34 39238855
33 625252064
1 143902436
13 338440011
25 334146355
5 515606983
...

output:

4878171

result:

ok single line: '4878171'

Test #40:

score: 15
Accepted
time: 8ms
memory: 5884kb

input:

40 1000000000
300
34 290272040
11 654139182
15 574182947
32 483616706
23 30659851
7 688206175
33 677483533
20 245930698
16 854673531
5 415424827
23 516937655
2 347957583
4 76422831
29 693454243
24 109103102
19 755284863
16 509051878
8 373221893
35 422824677
1 923039234
37 493392984
2 648194620
12 12...

output:

23360164

result:

ok single line: '23360164'

Test #41:

score: 15
Accepted
time: 4ms
memory: 6032kb

input:

40 999992811
300
40 756167738
1 755422093
1 756075552
40 755448533
40 755699260
1 755699433
40 756570280
40 755364761
1 755246371
40 756081840
1 756154293
1 756152536
1 755866341
1 755312497
40 755640274
7 340135464
3 953017751
1 755712914
1 755664483
40 755797029
9 969531054
40 755779575
1 75564995...

output:

129414313

result:

ok single line: '129414313'

Test #42:

score: 15
Accepted
time: 8ms
memory: 5732kb

input:

40 1000000000
300
17 999998001
1 999997965
1 999997890
1 7932
5 505323503
40 999998121
1 999998027
1 999998002
9 999997972
1 999997920
40 999997891
30 7999
29 7999
31 999998062
1 999998144
40 999997890
40 999998033
1 999998006
21 999997999
40 999998031
40 8094
40 999997995
13 999998024
40 999997875
...

output:

209640461

result:

ok single line: '209640461'

Test #43:

score: 15
Accepted
time: 4ms
memory: 5860kb

input:

40 1000000000
300
23 549509844
40 95786908
40 39290135
13 992491098
26 87052294
40 231331522
19 288109792
23 482918072
1 27192653
25 931473083
40 1
12 695623563
8 518257580
1 40343403
40 271412132
40 24291430
1 776119616
29 837580112
5 24636122
2 883373187
31 209930451
37 133788324
1 224219724
1 138...

output:

21898080

result:

ok single line: '21898080'

Test #44:

score: 15
Accepted
time: 8ms
memory: 5924kb

input:

40 1000000000
300
6 366666665
15 300000001
24 233333337
1 966666667
25 853754960
23 766666669
30 233333334
24 433333334
15 566666670
14 233333334
34 233333335
32 166666668
37 366666664
30 337173509
30 100000002
31 33333334
17 500000004
15 834459573
22 773895258
32 900000001
35 100000002
40 500000001...

output:

53549258

result:

ok single line: '53549258'

Subtask #4:

score: 0
Time Limit Exceeded

Test #45:

score: 0
Time Limit Exceeded

input:

1000000000 1000000000
17
822413671 70423910
260075513 431043546
300945721 793553248
142848049 163787897
392462410 831950868
699005697 111397300
444396260 130450496
642691616 595456084
467968916 463598810
159764248 611476406
929313754 539645102
365153650 964108073
906780716 373514044
970118116 655138...

output:

result:

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-29 16:31:01 | 开源项目