QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359048#5076. Prof. Pang and AntswdnmdwrnmmpTL 6194ms3856kbC++141.6kb2024-03-20 11:30:322024-03-20 11:30:34

Judging History

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

  • [2024-03-20 11:30:34]
  • 评测
  • 测评结果:TL
  • 用时:6194ms
  • 内存:3856kb
  • [2024-03-20 11:30:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

const int inf=1e18;
void solve(){
	int n,m; cin>>n>>m;
	vi a(n),b(n);
	rep(i,0,n-1){
		cin>>a[i];
	}
	auto chk=[&](int mid){
		auto cchk=[&]()->int{
			vector< array<int,2> > msg;
			rep(i,0,n-1){
				msg.pb({1+a[i],1});
				msg.pb({b[i]+a[i]+1,-1});
				msg.pb({b[i]+1-a[i]-1,2});
				msg.pb({mid-a[i]+1-1,-2});
			}
			sort(msg.begin(),msg.end());
			int res=0,rst=0,ls=-inf;
			int cnt0=0,cnt1=0;
			for(auto x:msg){
				int t=x[0]-ls;
				res+=t*min(cnt0,cnt1);
				int nxt=max(0ll, rst+(cnt0-cnt1)*t );
				if(nxt<rst){
					res+=rst-nxt;
				}
				rst=nxt,ls=x[0];
				if(x[1]==1){
					cnt0++;
				}
				else if(x[1]==-1){
					cnt0--;
				}
				else if(x[1]==2){
					cnt1++;
				}
				else{
					cnt1--;
				}
			}
			return res>=m;
		};
		auto dfs=[&](auto self,int d)->int{
			if(d==n){
				if(cchk()){
					return 1;
				}
				return 0;
			}
			rep(x,mid/2,(mid+1)/2){
				b[d]=x;
				if(self(self,d+1)){
					return 1;
				}
			}
			return 0;
		};
		return dfs(dfs,0);
	};
	int l=0,r=(*max_element(a.begin(),a.end())+m/n+1)*2;
	while(l<r){
		int mid=(l+r)/2;
		if(chk(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	int t; cin>>t;
	while(t--){
		solve();
	}
}

詳細信息

Test #1:

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

input:

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

output:

6
9
4

result:

ok 3 number(s): "6 9 4"

Test #2:

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

input:

1
1 100000000000000
1000000000

output:

200000000000000

result:

ok 1 number(s): "200000000000000"

Test #3:

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

input:

1
10 1
1 1 1 1 1 1 1 1 1 1

output:

4

result:

ok 1 number(s): "4"

Test #4:

score: 0
Accepted
time: 101ms
memory: 3856kb

input:

100000
1 76
95
1 60
68
1 81
86
1 88
67
1 69
28
1 75
65
1 56
22
1 88
60
1 51
41
1 64
11
1 54
71
1 63
19
1 88
5
1 89
66
1 80
66
1 81
48
1 67
99
1 94
36
1 54
46
1 51
37
1 82
17
1 74
41
1 69
61
1 79
65
1 78
10
1 71
17
1 87
88
1 83
2
1 58
29
1 59
43
1 78
53
1 75
73
1 77
71
1 52
82
1 63
69
1 83
19
1 61
27...

output:

267
197
254
223
138
206
112
209
134
128
197
126
176
222
213
178
266
188
147
126
164
157
192
210
156
142
264
166
117
146
185
222
220
217
202
166
122
162
250
214
160
158
220
132
108
213
198
276
226
197
204
140
146
215
122
142
201
269
269
188
144
246
251
200
217
184
192
139
234
128
190
242
254
166
152
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 201ms
memory: 3756kb

input:

100000
2 87
72 38
2 73
58 25
2 84
71 78
2 91
83 34
2 56
26 24
2 63
97 73
2 67
11 91
2 56
44 55
2 67
34 53
2 93
19 72
2 55
29 91
2 78
2 70
2 56
28 83
2 77
33 5
2 98
60 76
2 63
82 59
2 82
50 72
2 73
91 40
2 85
97 41
2 60
35 14
2 86
51 74
2 61
52 37
2 96
35 45
2 85
23 15
2 96
45 92
2 96
76 4
2 58
55 98...

output:

155
121
192
160
79
203
114
128
122
132
114
101
113
78
186
174
164
154
168
80
169
121
129
85
186
118
169
207
114
166
165
150
98
129
183
171
225
158
117
94
88
190
119
128
187
112
187
184
138
177
166
149
76
179
125
102
64
99
188
185
126
128
88
80
87
150
127
191
102
166
214
96
116
122
187
206
120
122
98...

result:

ok 100000 numbers

Test #6:

score: 0
Accepted
time: 335ms
memory: 3488kb

input:

100000
3 87
37 25 86
3 94
64 78 24
3 55
89 60 41
3 64
54 100 33
2 74
13 95
2 83
89 17
2 51
81 64
2 97
1 91
3 82
41 61 94
3 66
3 50 46
3 84
49 45 48
2 62
6 54
3 67
6 73 7
2 95
44 48
3 80
84 21 42
2 94
11 97
2 79
98 87
3 91
44 31 21
2 84
63 15
3 75
80 57 96
2 87
93 74
2 74
69 19
2 80
18 38
2 96
87 30
...

output:

107
136
130
120
122
127
172
127
144
78
124
82
67
141
104
136
226
96
115
176
212
113
97
157
132
140
104
105
116
174
116
114
91
85
166
133
94
70
185
104
140
117
90
168
116
108
152
127
130
167
97
155
87
76
225
136
149
103
75
187
161
104
98
113
81
120
112
94
97
130
156
60
97
95
200
100
132
89
147
126
21...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 704ms
memory: 3496kb

input:

100000
4 90
14 97 74 38
4 54
21 15 46 16
3 86
95 74 59
3 86
42 64 31
3 66
94 100 60
3 83
92 13 77
3 81
80 32 9
3 52
42 48 41
4 64
90 68 23 1
3 76
80 71 1
4 79
7 71 17 86
4 81
22 1 20 96
3 68
70 28 54
4 87
27 1 66 51
3 65
47 74 55
4 87
6 14 56 89
3 96
64 57 64
3 52
25 95 48
4 85
98 71 33 8
3 59
3 1 5...

output:

98
54
177
117
187
116
83
106
64
100
79
59
117
78
136
75
157
100
85
59
64
119
129
127
134
159
88
101
172
87
124
56
101
91
130
109
76
70
113
127
65
145
112
85
126
88
157
162
98
98
119
131
71
101
106
102
64
130
144
138
106
144
96
76
95
70
82
86
109
43
172
64
100
88
97
64
165
74
97
163
87
74
126
62
110
...

result:

ok 100000 numbers

Test #8:

score: 0
Accepted
time: 1182ms
memory: 3796kb

input:

100000
3 52
91 84 66
3 55
47 65 9
5 93
20 100 49 93 100
5 68
51 47 88 33 33
4 62
26 65 53 80
4 85
88 52 51 70
5 79
66 27 7 29 87
5 84
86 82 11 45 23
5 67
43 87 96 62 79
3 99
85 59 49
3 59
19 20 57
5 64
73 18 62 57 61
5 96
10 11 7 1 79
3 63
77 57 6
3 93
13 76 22
5 71
18 72 37 72 19
4 91
54 51 70 88
5...

output:

177
75
117
99
111
145
70
77
140
159
70
101
48
85
92
74
148
117
64
123
54
101
86
50
108
105
169
100
66
85
53
98
113
86
130
99
115
75
87
62
131
88
72
113
96
87
73
88
106
197
106
87
79
93
99
104
129
81
82
73
100
84
96
132
84
91
93
158
169
89
67
118
84
73
95
87
118
48
90
104
107
119
89
66
93
56
62
110
1...

result:

ok 100000 numbers

Test #9:

score: 0
Accepted
time: 2113ms
memory: 3552kb

input:

83333
6 55
56 67 50 53 91 87
5 99
16 62 37 23 4
5 53
100 45 65 26 45
6 54
12 32 96 87 36 75
5 90
84 82 26 11 34
5 85
16 61 18 63 37
6 100
48 25 1 9 29 63
6 70
17 17 96 31 8 21
5 80
32 94 43 19 91
5 51
88 29 41 92 9
5 53
26 62 51 31 7
5 81
45 3 56 26 81
5 79
83 78 24 26 20
4 88
89 33 92 49
5 90
79 77...

output:

126
64
96
72
79
77
58
50
91
65
61
74
74
127
106
61
44
58
61
169
126
71
116
108
41
75
111
97
88
50
108
113
72
115
100
98
70
78
93
91
80
64
125
64
76
59
96
107
69
92
71
75
112
88
100
148
105
79
80
68
83
46
56
96
40
88
44
79
67
85
84
54
84
86
78
131
102
74
59
66
51
100
106
95
58
156
134
84
131
55
68
58...

result:

ok 83333 numbers

Test #10:

score: 0
Accepted
time: 3125ms
memory: 3492kb

input:

71428
4 67
32 43 42 20
4 81
56 97 53 77
5 87
62 29 93 48 31
5 60
6 62 75 69 45
6 64
2 70 14 99 96 12
4 53
41 23 99 97
6 65
47 49 14 18 7 42
7 52
45 55 16 61 38 64 100
6 76
60 26 15 93 79 63
5 67
24 83 11 37 13
5 65
19 6 30 17 8
4 77
73 95 17 54
4 57
18 42 86 52
6 68
42 71 17 12 70 7
4 86
88 2 78 44
...

output:

86
151
102
75
43
92
49
81
80
56
43
111
90
48
90
126
117
59
87
54
72
79
59
81
95
78
105
72
59
85
132
99
122
76
51
117
122
75
46
74
61
145
116
84
110
114
78
76
135
89
93
64
77
67
68
100
78
152
81
98
157
89
158
58
48
71
170
90
77
70
112
44
52
103
70
48
96
58
45
67
63
60
38
56
107
48
83
121
101
112
58
1...

result:

ok 71428 numbers

Test #11:

score: 0
Accepted
time: 6194ms
memory: 3532kb

input:

62500
6 66
13 26 30 76 55 74
8 92
87 100 71 60 24 47 38 1
5 87
81 67 74 92 30
5 83
32 81 57 46 8
8 92
72 90 47 24 14 82 74 3
6 57
58 36 74 64 96 87
6 59
50 48 63 19 4 50
7 91
4 39 50 60 90 13 51
5 81
30 49 88 52 21
6 55
38 67 64 92 54 4
7 85
96 55 76 56 58 97 17
8 54
54 18 55 25 43 82 94 27
7 72
64 ...

output:

69
73
142
83
60
124
56
67
93
66
115
66
74
58
97
81
107
59
58
96
67
70
79
63
58
78
77
66
101
55
83
94
68
48
94
81
88
89
73
58
69
74
132
75
55
93
34
56
64
70
96
61
64
80
64
83
56
86
63
88
113
80
75
54
93
76
116
53
38
75
117
78
92
52
104
46
106
57
100
89
55
104
81
60
59
41
62
127
66
72
67
91
73
67
78
1...

result:

ok 62500 numbers

Test #12:

score: -100
Time Limit Exceeded

input:

55555
5 70
78 5 18 31 38
8 90
78 24 11 88 90 74 69 91
5 87
97 64 24 82 13
9 74
99 58 51 44 83 12 100 71 51
7 62
17 32 67 28 100 14 72
6 58
32 78 48 68 94 55
8 80
84 62 20 53 48 30 82 70
5 95
14 4 89 18 64
5 61
63 86 82 89 8
8 64
20 18 78 39 30 49 43 9
9 94
67 8 78 13 6 63 78 97 49
6 98
99 14 29 30 6...

output:

59
86
84
94
61
110
91
64
89
54
60
83
134
64
57
62
33
71
87
92
89
66
52
54
52
119
146
82
50
57
84
81
75
94
60
99
86
52
79
127
59
71
118
54
46
68
64
84
138
104
55
68
82
67
44
49
83
65
52
62
68
100
97
44
44
43
111
116
36
85
28
49
42
28
89
40
73
44
48
92
116
37
67
63
63
87
129
79
53
45
76
51
53
54
62
52...

result: