QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111949#3142. Semiexpressminhcool100 ✓10ms13556kbC++172.1kb2023-06-09 10:55:242023-06-09 10:55:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 10:55:25]
  • 评测
  • 测评结果:100
  • 用时:10ms
  • 内存:13556kb
  • [2023-06-09 10:55:24]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, m, k;
int a, b, c;
int t;
int arr[N];

int cal[N][N];

void process(){
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> t;
	for(int i = 1; i <= m; i++) cin >> arr[i];
	sort(arr + 1, arr + m + 1);
	k -= m;
	arr[m + 1] = n + 1;
	for(int i = 1; i <= m; i++){
		int val = (t - b * (arr[i] - 1));
	//	cout << i << " " << val << "\n";
		if(val < 0) break;
		int diff = arr[i + 1] - arr[i];
		//cout << "OK " << i << " " << val << " " << diff << "\n";
		if(((diff - 1) * a) <= val){
			cal[i][0] = diff;
			continue;
		} 
		else cal[i][0] = (val / a) + 1;
		int lst = arr[i] + (val / a);
		for(int j = 1; j <= k; j++){
			//val ;
			int val2 = val - ((lst + 1 - arr[i]) * c);
		//	cout << i << " " << j << " " << val2 << "\n";
			//val = ( + l)
			if(val2 < 0) break;
			int nxt = min(arr[i + 1] - 1, lst + 1 + val2 / a);
			cal[i][j] = nxt - lst;
			if(nxt == arr[i + 1] - 1) break;
			lst = nxt;
		}
	}
	/*
	for(int i = 1; i <= m; i++){
		for(int j = 0; j <= k; j++) cout << i << " " << j << " " << cal[i][j] << "\n";
	}*/
	//exit(0);
	vector<int> cnt(m + 1);
	priority_queue<ii, vector<ii>> pq;
	int answer = 0;
	for(int i = 1; i <= m; i++) answer += cal[i][0];
	for(int i = 1; i <= m; i++) cnt[i] = 1;
	for(int i = 1; i <= m; i++) pq.push({cal[i][1], i});
	for(int i = 1; i <= k; i++){
		if(pq.empty()) break;
		ii temp = pq.top();
		pq.pop();
		answer += temp.fi;
		cnt[temp.se]++;
		if(cnt[temp.se] <= k) pq.push({cal[temp.se][cnt[temp.se]], temp.se});
	}
	cout << answer - 1 << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 18
Accepted

Test #1:

score: 18
Accepted
time: 2ms
memory: 3356kb

input:

300 10 12
305968 117630 122513
1000000000
1
70
77
132
185
239
257
267
286
300

output:

299

result:

ok single line: '299'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

300 19 21
722383 233583 721658
40029820
1
8
19
35
53
54
58
76
87
90
91
111
137
189
190
212
242
271
300

output:

141

result:

ok single line: '141'

Test #3:

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

input:

300 95 97
661199 261739 262075
71276376
1
74
96
110
111
112
118
127
134
137
140
141
148
153
155
158
162
163
165
168
169
174
177
180
181
183
184
185
188
189
190
191
193
195
198
202
204
206
207
208
209
210
211
212
213
214
218
220
221
222
226
227
230
232
235
237
238
241
242
244
246
249
250
251
255
256
...

output:

272

result:

ok single line: '272'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

300 14 16
595662 371803 372602
1
1
105
183
197
220
230
242
252
254
264
270
280
288
300

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

300 19 21
100000 10 20
3000
1
11
12
17
23
26
48
50
65
76
107
113
116
150
164
166
200
251
300

output:

20

result:

ok single line: '20'

Test #6:

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

input:

300 27 29
1000 12 34
492593208
1
30
85
140
148
152
156
168
169
178
203
240
245
249
250
252
256
259
263
267
270
274
294
296
297
298
300

output:

299

result:

ok single line: '299'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

300 21 23
899043 351059 351526
105317699
1
4
7
15
17
18
21
24
30
38
46
51
70
74
76
107
110
125
143
162
300

output:

269

result:

ok single line: '269'

Test #8:

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

input:

300 30 32
833508 536610 537542
160982999
1
5
14
15
17
19
25
27
29
35
36
47
48
55
56
66
74
76
87
88
93
96
112
125
129
133
150
151
212
300

output:

296

result:

ok single line: '296'

Subtask #2:

score: 30
Accepted

Test #9:

score: 30
Accepted
time: 2ms
memory: 3412kb

input:

300 10 75
433522847 9778790 213751348
129728243
1
20
82
87
116
118
243
287
292
300

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

300 20 222
615523476 433457304 615522486
14485468224
1
3
18
20
26
28
39
44
57
60
62
64
71
76
89
111
116
140
146
300

output:

31

result:

ok single line: '31'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

300 27 201
933391758 382020377 382020976
6708439420
1
87
126
129
149
172
189
203
205
214
226
228
252
256
258
259
261
272
275
279
280
285
288
289
291
293
300

output:

17

result:

ok single line: '17'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

300 37 118
615653620 433326230 615653556
15724684805
1
20
28
94
118
160
166
177
194
200
205
206
216
221
226
228
231
236
238
242
253
254
255
260
271
274
275
279
280
285
289
290
291
292
293
295
300

output:

33

result:

ok single line: '33'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3452kb

input:

300 24 183
1000 30 100
23504
1
20
30
32
39
60
76
84
98
113
123
138
141
159
163
167
176
201
211
246
279
290
299
300

output:

299

result:

ok single line: '299'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

300 19 21
345 67 89
20099
1
2
23
61
63
107
108
114
116
125
148
187
196
204
220
226
289
299
300

output:

255

result:

ok single line: '255'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

300 22 24
120120 100 1000
1999999
1
7
14
19
48
79
80
92
109
120
129
130
142
143
172
192
199
206
225
271
282
300

output:

257

result:

ok single line: '257'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3480kb

input:

300 29 31
10000000 123 456
99999999
1
4
23
27
28
36
42
44
51
54
78
89
93
113
129
133
150
156
174
201
232
233
242
251
265
268
281
295
300

output:

215

result:

ok single line: '215'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3360kb

input:

300 27 113
935095687 375597634 375598474
14461930877
1
91
101
132
171
179
191
201
203
207
227
231
233
235
240
244
246
248
250
259
267
270
276
288
296
297
300

output:

38

result:

ok single line: '38'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

300 31 160
935030150 375925845 375926148
35349754506
1
11
15
24
29
38
40
41
42
50
53
58
59
64
81
84
90
91
98
101
120
124
128
129
134
151
163
171
228
235
300

output:

94

result:

ok single line: '94'

Subtask #3:

score: 52
Accepted

Test #19:

score: 52
Accepted
time: 2ms
memory: 4496kb

input:

1000000000 1500 1925
443746647 102966190 110988888
18198258829222562
1
35260
4099706
4948659
5008441
5435083
5967067
6102207
6815150
7165470
7817850
7848198
8884040
8990491
9270205
10570006
10984486
11487776
11727122
11817897
12332094
13280626
13831505
13918141
13933119
14079325
14438945
16011322
16...

output:

176702472

result:

ok single line: '176702472'

Test #20:

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

input:

1000000000 1400 2415
604774864 443681104 604774226
72228650932226906
1
130569
455891
679662
1948347
2444146
3129707
4214005
5691950
10084869
10087818
11397646
12388787
13228156
13415408
13552051
14465388
15380405
16368325
16559031
17065769
17270039
17997314
18216569
19353265
19364954
19553622
204125...

output:

162531741

result:

ok single line: '162531741'

Test #21:

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

input:

1000000000 1300 1302
100000000 5 10
500000000
1
234337
1419485
1488894
3260754
5182794
5641815
7043835
7413918
8581015
9056400
9242151
10412268
11266964
11828740
11897944
13222561
14192632
14869296
15037887
16985357
18430977
19396138
20471392
22692080
22754041
23535271
24954310
25657230
26114753
262...

output:

386

result:

ok single line: '386'

Test #22:

score: 0
Accepted
time: 3ms
memory: 4456kb

input:

1000000000 1595 1699
1010101 101 10101
5000000000
1
368929
673260
784927
966735
985353
1115466
1213659
1333151
2866300
2878515
3438988
3471078
4302536
4436214
4444369
4670318
4776951
5094679
5209487
5492451
5671704
5820131
6537385
6655383
6702724
6859853
7018569
7056497
7344786
7942598
8323995
94490...

output:

959284

result:

ok single line: '959284'

Test #23:

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

input:

1000000000 1696 2321
135246789 10 123
199999999999
1
32190287
34045366
41373130
44305326
57216518
80405681
82844903
90760312
104519545
117407089
117413729
126334602
134654118
147032267
156066801
179227381
187929950
191821815
195182064
197977838
200338159
202583115
204370862
211479029
217487825
21893...

output:

3333503

result:

ok single line: '3333503'

Test #24:

score: 0
Accepted
time: 2ms
memory: 8384kb

input:

1000000000 1245 1249
12483579 34 5678
28190377415
1
525955
974228
1905153
2537916
2582081
2611066
2647757
2891288
3043591
3163198
3712311
5164047
5862650
5937520
6354712
6571655
6916419
6971596
7057104
7426923
7999460
8375329
8660461
8828821
8953388
9345191
9902604
10167736
10383714
10501464
1170771...

output:

1909602

result:

ok single line: '1909602'

Test #25:

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

input:

1000000000 993 994
945450573 323823522 323823884
18432265838437394
1
123730
44124054
53708297
69566659
76973095
79242096
102590105
108605385
120908519
134107222
134834501
169173460
170223076
171293381
189925301
196113679
198857987
201374512
207720533
207894366
218463938
221469686
224218368
227316982...

output:

37850767

result:

ok single line: '37850767'

Test #26:

score: 0
Accepted
time: 3ms
memory: 11340kb

input:

1000000000 1993 1994
605692549 445385043 605691724
341066094031827843
1
180212
297786
1128906
1152820
1186761
1366676
1382354
1448818
1520015
1593192
1776788
1908807
2584325
2587444
2699812
2901400
2958555
3016266
3117546
3868767
4839067
4921467
5172217
5231077
6059689
6885246
7084693
7121945
751583...

output:

765029010

result:

ok single line: '765029010'

Test #27:

score: 0
Accepted
time: 2ms
memory: 9520kb

input:

100000000 1500 1502
100000000 4 8
1753086419
1
5694
32184
44140
157803
215014
240552
322549
336670
625697
628828
648496
683398
804614
839030
862619
921403
937209
954874
958191
1075304
1134147
1243336
1331987
1344135
1389894
1417706
1427026
1430571
1633151
1869103
1951036
1974003
1997774
2054630
2158...

output:

24063

result:

ok single line: '24063'

Test #28:

score: 0
Accepted
time: 2ms
memory: 9584kb

input:

1000000000 1555 1557
123456789 2 9
1949396398
1
1080314
1240512
1643986
1764050
1990497
2772850
3173329
3617521
4668963
5622957
5981124
6599305
6677972
7276679
7401014
7754842
8078422
8541656
11396627
11561156
12065139
13455444
15943530
16499690
16869514
17525705
17884912
17977637
18840406
19878980
...

output:

12736

result:

ok single line: '12736'

Test #29:

score: 0
Accepted
time: 3ms
memory: 7752kb

input:

1000000000 500 1096
10000000 1 30
1999999999
1
1975881
1988362
2743933
8368494
8664618
9196856
14048832
17369780
18158696
23645206
24545820
31517438
32096142
34279452
35596835
38448508
39912021
46160161
46266720
49916716
54050706
57342230
57839673
58195604
58256694
69155006
69233215
69389085
7175378...

output:

194444

result:

ok single line: '194444'

Test #30:

score: 0
Accepted
time: 3ms
memory: 5184kb

input:

1000000000 100 1970
10000000 1 27
1999999999
1
5986618
10657050
12442216
14905254
27018583
47366067
48003323
60523105
62412674
63632296
70643103
78237598
81073431
99868566
101115740
102291729
128259617
132193942
138209872
146561091
184641481
208006177
222428135
257540486
261046557
284675680
29320655...

output:

388803

result:

ok single line: '388803'

Extra Test:

score: 0
Extra Test Passed