QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#111949 | #3142. Semiexpress | minhcool | 100 ✓ | 10ms | 13556kb | C++17 | 2.1kb | 2023-06-09 10:55:24 | 2023-06-09 10:55:25 |
Judging History
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