QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #646925 | #1206. IOIOI Cards | Grand_Elf | 100 ✓ | 83ms | 47612kb | C++17 | 1.8kb | 2024-10-17 10:01:35 | 2024-10-17 10:01:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 5;
const int N = 5e5 + 5;
const long long inf = 1e18;
int n, m, a[6], l[M], r[M];
long long ans, dis[6][N], val[6][6];
bool vis[6][N];
vector<int> e[N];
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > q;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 1; i <= 5; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
n = a[5] + 1;
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
e[l[i]].emplace_back(r[i] + 1);
e[r[i] + 1].emplace_back(l[i]);
}
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= 4; i++) {
int s = a[i] + 1;
dis[i][s] = 0;
q.push(make_pair(0ll, s));
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[i][u]) {
continue;
}
vis[i][u] = 1;
for (int v : e[u]) {
int w = abs(u - v);
if (dis[i][v] > dis[i][u] + w) {
dis[i][v] = min(dis[i][v], dis[i][u] + w);
q.push(make_pair(dis[i][v], v));
}
}
}
for (int j = 1; j <= 5; j++) {
if (!vis[i][a[j] + 1] || j == i) {
val[i][j] = inf;
} else {
val[i][j] = dis[i][a[j] + 1];
}
}
}
ans = inf;
ans = min(ans, val[1][5] + val[2][5] + val[3][5] + val[4][5]);
ans = min(ans, val[1][2] + val[3][5] + val[4][5]);
ans = min(ans, val[1][3] + val[2][5] + val[4][5]);
ans = min(ans, val[1][4] + val[2][5] + val[3][5]);
ans = min(ans, val[2][3] + val[1][5] + val[4][5]);
ans = min(ans, val[2][4] + val[1][5] + val[3][5]);
ans = min(ans, val[3][4] + val[1][5] + val[2][5]);
ans = min(ans, val[1][2] + val[3][4]);
ans = min(ans, val[1][3] + val[2][4]);
ans = min(ans, val[1][4] + val[2][3]);
cout << (ans == inf ? -1 : ans) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 0ms
memory: 39764kb
input:
1366 26952 456 8932 44227 10 25791 41655 32148 47560 40440 73918 96 45006 55177 61271 1228 42333 645 30218 8636 49576 15882 77955 10343 16005
output:
-1
result:
ok single line: '-1'
Test #2:
score: 15
Accepted
time: 3ms
memory: 39728kb
input:
100000 100000 100000 100000 100000 10 129399 271451 311676 472059 342782 379302 125106 267050 120919 175453 55318 88285 154907 168427 219643 387548 15549 486064 32313 249420
output:
-1
result:
ok single line: '-1'
Test #3:
score: 15
Accepted
time: 4ms
memory: 41684kb
input:
1 1 1 1 1 10 2 3 3 4 1 2 3 4 3 4 1 5 4 5 3 3 1 4 2 4
output:
4
result:
ok single line: '4'
Test #4:
score: 15
Accepted
time: 9ms
memory: 40188kb
input:
95360 78988 71508 15756 32444 10 95361 261612 95361 148112 52581 95360 174349 261612 52581 174348 245857 261612 148113 245856 119840 261612 19949 261612 52581 261612
output:
180304
result:
ok single line: '180304'
Test #5:
score: 15
Accepted
time: 4ms
memory: 39848kb
input:
100000 100000 100000 100000 100000 10 100001 200000 100001 300000 195544 200000 72737 200000 300001 400000 94206 300000 72737 314605 314606 396588 35778 314605 72737 94205
output:
200000
result:
ok single line: '200000'
Test #6:
score: 15
Accepted
time: 0ms
memory: 39648kb
input:
1 1 1 1 1 10 2 2 2 3 2 5 1 1 3 4 1 2 4 5 1 3 5 5 1 4
output:
4
result:
ok single line: '4'
Test #7:
score: 15
Accepted
time: 0ms
memory: 40148kb
input:
40703 91558 63295 11141 69164 7 40704 132261 40704 206697 40704 125908 132262 195556 125909 132261 195557 206697 125909 206697
output:
102699
result:
ok single line: '102699'
Test #8:
score: 15
Accepted
time: 6ms
memory: 41796kb
input:
3 3 2 1 3 10 4 6 1 6 7 10 3 6 2 6 6 8 10 10 1 5 6 7 3 12
output:
22
result:
ok single line: '22'
Test #9:
score: 15
Accepted
time: 6ms
memory: 41976kb
input:
20984 63019 95929 88991 68140 10 181796 268923 27239 181795 80929 181795 27239 268923 20985 268923 20985 80928 166304 227593 84004 227593 84004 166303 84004 179932
output:
343868
result:
ok single line: '343868'
Test #10:
score: 15
Accepted
time: 4ms
memory: 41728kb
input:
89138 65363 17547 94834 57361 10 10158 89138 125844 200171 50849 200171 113540 200171 200172 266882 125844 154501 50849 172048 50849 154501 172049 266882 154502 266882
output:
-1
result:
ok single line: '-1'
Test #11:
score: 15
Accepted
time: 4ms
memory: 41740kb
input:
1 1 2 1 1 2 2 5 3 4
output:
6
result:
ok single line: '6'
Test #12:
score: 15
Accepted
time: 0ms
memory: 39784kb
input:
1 1 1 2 1 2 2 2 4 5
output:
3
result:
ok single line: '3'
Test #13:
score: 15
Accepted
time: 0ms
memory: 41740kb
input:
2 1 1 1 2 2 3 4 4 5
output:
4
result:
ok single line: '4'
Test #14:
score: 15
Accepted
time: 4ms
memory: 40124kb
input:
2 5 1 5 1 10 3 8 8 13 9 13 1 1 2 2 1 3 3 3 1 2 1 1 1 1
output:
12
result:
ok single line: '12'
Test #15:
score: 15
Accepted
time: 0ms
memory: 41976kb
input:
100000 100000 100000 100000 100000 10 100001 300000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000
output:
400000
result:
ok single line: '400000'
Subtask #2:
score: 50
Accepted
Test #16:
score: 50
Accepted
time: 14ms
memory: 41508kb
input:
42 1 21 3 9 100000 7 33 12 39 41 56 13 21 25 69 43 44 12 58 62 66 33 36 2 30 18 66 4 76 47 60 12 23 5 24 7 58 19 61 27 55 20 70 15 33 33 35 25 68 42 43 37 72 14 70 7 17 12 14 8 43 5 7 7 45 13 22 18 49 8 60 27 74 2 7 64 73 30 57 31 58 25 53 20 56 8 72 46 61 50 61 52 61 1 12 4 47 28 30 32 41 18 29 6 2...
output:
4
result:
ok single line: '4'
Test #17:
score: 50
Accepted
time: 13ms
memory: 41332kb
input:
50 50 50 50 50 100000 8 49 40 204 199 201 63 222 54 183 11 241 77 235 94 238 114 233 101 213 56 83 85 175 131 141 17 228 211 241 80 136 24 99 20 234 68 69 3 89 76 221 36 41 120 186 144 166 23 248 7 224 90 109 27 54 43 242 96 131 18 212 6 180 87 195 163 211 50 169 37 197 6 92 20 172 191 195 100 230 1...
output:
100
result:
ok single line: '100'
Test #18:
score: 50
Accepted
time: 12ms
memory: 43116kb
input:
1 1 1 1 1 100000 3 4 1 2 4 5 1 4 2 2 3 3 1 1 1 1 5 5 4 5 1 2 2 2 2 4 5 5 2 4 2 3 5 5 2 2 4 4 3 4 1 1 1 3 3 3 1 1 1 3 3 4 1 5 1 1 1 4 2 5 3 3 3 4 2 3 1 2 4 4 1 2 2 2 5 5 1 1 1 3 3 3 5 5 3 4 1 1 2 3 1 3 1 4 1 1 4 4 5 5 1 1 5 5 1 3 2 2 1 5 1 2 2 3 2 2 2 5 2 2 2 4 1 3 2 4 3 3 5 5 4 4 1 3 4 4 3 5 1 2 1 3...
output:
2
result:
ok single line: '2'
Test #19:
score: 50
Accepted
time: 9ms
memory: 39832kb
input:
39 30 3 15 31 2345 16 39 40 114 20 39 40 100 40 99 40 52 40 117 18 39 12 39 40 73 40 92 40 41 40 105 40 53 10 39 24 39 40 113 40 109 40 47 40 58 23 39 9 39 40 71 40 61 40 46 38 39 40 90 22 39 37 39 31 39 40 89 27 39 40 104 40 84 35 39 40 76 33 39 40 98 21 39 6 39 40 62 40 82 28 39 40 107 40 91 40 11...
output:
45
result:
ok single line: '45'
Test #20:
score: 50
Accepted
time: 4ms
memory: 40536kb
input:
50 50 50 50 50 31375 51 100 51 150 51 200 16 50 27 50 35 50 51 214 51 170 51 107 51 231 28 50 51 85 51 153 51 68 51 83 51 201 51 169 8 50 49 50 51 229 51 189 51 165 51 180 51 149 51 247 51 196 51 154 51 193 51 90 51 122 51 219 17 50 51 157 51 120 51 66 51 142 48 50 51 178 51 51 51 111 51 248 51 206 ...
output:
100
result:
ok single line: '100'
Test #21:
score: 50
Accepted
time: 0ms
memory: 40584kb
input:
50 50 50 50 50 10000 51 100 51 150 51 139 44 50 51 111 51 168 51 143 18 50 51 81 51 85 51 119 51 188 51 195 51 230 51 215 51 151 51 247 46 50 51 145 51 211 51 216 51 234 12 50 51 212 51 108 51 223 51 67 51 130 51 116 51 154 51 199 22 50 34 50 51 80 51 162 51 65 51 174 51 163 42 50 51 232 51 187 51 1...
output:
100
result:
ok single line: '100'
Test #22:
score: 50
Accepted
time: 3ms
memory: 41848kb
input:
50 50 50 50 50 5000 66 142 66 203 66 244 66 85 43 65 66 137 66 122 66 75 63 65 66 219 66 107 66 113 66 72 32 65 66 178 66 191 66 68 66 163 66 143 66 212 66 134 66 105 66 204 66 82 55 65 46 65 59 65 66 242 66 158 56 65 82 233 86 233 43 233 162 233 138 233 155 233 76 233 177 233 234 249 63 233 220 233...
output:
100
result:
ok single line: '100'
Test #23:
score: 50
Accepted
time: 0ms
memory: 40324kb
input:
50 50 50 50 50 3000 6 147 47 147 113 147 148 221 16 147 148 153 148 236 117 147 148 205 148 248 76 147 141 147 148 231 148 163 134 147 148 247 53 147 148 181 148 176 142 147 41 147 69 147 148 168 148 230 83 147 72 147 148 180 35 147 145 147 101 147 6 46 6 112 6 221 6 57 6 94 6 205 6 248 6 75 6 231 6...
output:
-1
result:
ok single line: '-1'
Test #24:
score: 50
Accepted
time: 7ms
memory: 43260kb
input:
50 50 50 50 50 100000 51 163 51 138 101 172 101 182 17 150 191 200 174 200 183 200 18 237 18 54 18 166 33 114 117 226 227 235 13 226 153 176 39 152 153 197 125 163 27 237 226 237 46 237 139 192 91 222 183 236 124 225 55 114 39 97 39 45 17 235 118 229 44 225 57 241 57 113 61 124 13 97 27 182 14 37 38...
output:
268
result:
ok single line: '268'
Test #25:
score: 50
Accepted
time: 7ms
memory: 43080kb
input:
50 50 50 50 50 100000 51 150 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200 101 200...
output:
200
result:
ok single line: '200'
Test #26:
score: 50
Accepted
time: 0ms
memory: 40116kb
input:
38 33 15 42 26 2 39 128 72 86
output:
105
result:
ok single line: '105'
Test #27:
score: 50
Accepted
time: 0ms
memory: 41744kb
input:
28 20 9 2 18 2 29 48 58 59
output:
22
result:
ok single line: '22'
Test #28:
score: 50
Accepted
time: 0ms
memory: 39780kb
input:
5 33 37 33 1 2 6 75 39 108
output:
140
result:
ok single line: '140'
Test #29:
score: 50
Accepted
time: 3ms
memory: 41772kb
input:
50 50 50 50 50 102 51 250 1 250 1 249 2 249 2 248 3 248 3 247 4 247 4 246 5 246 5 245 6 245 6 244 7 244 7 243 8 243 8 242 9 242 9 241 10 241 10 240 11 240 11 239 12 239 12 238 13 238 13 237 14 237 14 236 15 236 15 235 16 235 16 234 17 234 17 233 18 233 18 232 19 232 19 231 20 231 20 230 21 230 21 22...
output:
20300
result:
ok single line: '20300'
Subtask #3:
score: 35
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #30:
score: 35
Accepted
time: 30ms
memory: 44768kb
input:
36057 98320 45973 22651 32666 100000 10119 94989 97206 218513 177698 206766 92618 218876 7860 52997 31466 136516 16392 79723 147688 153963 108216 195674 59608 132092 201145 201733 78531 149105 155816 181645 71345 226059 132026 166092 21187 23488 135986 232476 21318 200516 29566 142451 146544 230028 ...
output:
-1
result:
ok single line: '-1'
Test #31:
score: 35
Accepted
time: 28ms
memory: 47612kb
input:
100000 100000 100000 100000 100000 100000 19051 192363 254149 451351 133890 160077 285471 370445 228224 467175 168051 276843 88708 250280 36040 434218 44328 87905 395270 413215 387329 477044 109083 321906 333282 333749 403526 492331 194212 393193 168898 463823 170836 375771 189613 322822 363330 3747...
output:
-1
result:
ok single line: '-1'
Test #32:
score: 35
Accepted
time: 83ms
memory: 45816kb
input:
57489 73388 27542 97421 74849 100000 13643 57489 57490 231611 130878 141279 130878 189515 122499 158419 158420 197130 69515 255840 54032 255840 206211 255840 145119 255840 51503 286110 281884 323006 156597 281883 281884 322780 281884 322030 157467 299088 24809 157466 286085 330194 26539 286084 28608...
output:
18865487
result:
ok single line: '18865487'
Test #33:
score: 35
Accepted
time: 25ms
memory: 45892kb
input:
19197 38636 726 18106 75369 98765 19198 70369 19198 22580 19198 71934 57834 102175 57834 75361 15807 57833 4544 58559 58560 120426 14976 76665 76666 131796 11385 76665 87866 128462 58080 128462 126527 128462 41020 128462 2869 62621 52480 62621 62622 131289 38446 109087 92460 113797 63310 113797 5801...
output:
-1
result:
ok single line: '-1'
Test #34:
score: 35
Accepted
time: 24ms
memory: 46912kb
input:
100000 100000 100000 100000 100000 100000 100001 129099 100001 318096 57000 200000 200001 281922 51337 200000 31150 200000 300001 476400 300001 344647 63188 300000 339645 400000 116277 434132 76550 116276 86004 454884 398755 454884 300085 454884 199622 284613 34622 199621 414321 485156 406115 485156...
output:
-1
result:
ok single line: '-1'
Test #35:
score: 35
Accepted
time: 29ms
memory: 44152kb
input:
100000 100000 100000 100000 100000 100000 100001 300000 100001 474095 100001 214630 100001 376919 100001 457919 100001 372786 100001 120658 100001 109985 100001 352224 83117 100000 100001 202428 71796 100000 100001 492578 65721 100000 100001 108575 100001 196116 100001 335433 65052 100000 100001 405...
output:
200000
result:
ok single line: '200000'
Test #36:
score: 35
Accepted
time: 13ms
memory: 43240kb
input:
100000 100000 100000 100000 100000 100000 100001 200000 100001 300000 100001 400000 47499 100000 100001 321893 100001 163131 100001 456726 100001 223809 100001 330068 70375 100000 100001 452495 100001 488967 100001 401608 86414 100000 100001 200895 25824 100000 100001 432216 100001 396329 100001 324...
output:
200000
result:
ok single line: '200000'
Test #37:
score: 35
Accepted
time: 60ms
memory: 45532kb
input:
100000 100000 100000 100000 100000 100000 236907 238139 57320 359880 12962 57319 316416 329542 262979 374691 374692 488471 15357 374691 57645 155606 57645 120766 47694 336210 47694 320944 47694 56130 77581 272875 43942 77580 72979 143954 72979 216810 72979 137091 49916 72978 24381 130175 383917 4654...
output:
11555326
result:
ok single line: '11555326'
Test #38:
score: 35
Accepted
time: 79ms
memory: 45460kb
input:
100000 100000 100000 100000 100000 100000 168706 417449 417450 473579 242756 417449 333935 417449 280565 417449 54575 417449 74476 233720 233721 475291 233721 369066 23531 233720 233721 316297 233721 286296 233721 280564 216754 463337 14677 463337 366674 463337 9963 463337 37867 463337 451683 463337...
output:
-1
result:
ok single line: '-1'
Test #39:
score: 35
Accepted
time: 79ms
memory: 45744kb
input:
100000 100000 100000 100000 100000 100000 100001 337686 100001 472646 93772 200000 300001 317105 84015 300000 300001 458454 108642 300000 78688 300000 267048 400000 8122 442644 8122 362067 83664 387990 83664 236259 452313 498202 110489 472952 110489 281635 9289 323627 88974 295991 29330 295991 14750...
output:
4622278
result:
ok single line: '4622278'
Test #40:
score: 35
Accepted
time: 12ms
memory: 43036kb
input:
100000 100000 100000 100000 100000 100000 100001 300000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001 400000 200001...
output:
400000
result:
ok single line: '400000'
Test #41:
score: 35
Accepted
time: 0ms
memory: 41764kb
input:
65517 24427 43786 33279 9178 2 65518 89944 133731 167009
output:
57706
result:
ok single line: '57706'
Test #42:
score: 35
Accepted
time: 0ms
memory: 39780kb
input:
30351 95338 38522 24408 9390 2 30352 164211 125690 188619
output:
196790
result:
ok single line: '196790'
Test #43:
score: 35
Accepted
time: 0ms
memory: 40048kb
input:
25860 40131 59164 74978 11739 2 25861 200133 65992 125155
output:
233437
result:
ok single line: '233437'
Test #44:
score: 35
Accepted
time: 26ms
memory: 45584kb
input:
100000 100000 100000 100000 100000 100000 100001 500000 1 500000 1 499999 2 499999 2 499998 3 499998 3 499997 4 499997 4 499996 5 499996 5 499995 6 499995 6 499994 7 499994 7 499993 8 499993 8 499992 9 499992 9 499991 10 499991 10 499990 11 499990 11 499989 12 499989 12 499988 13 499988 13 499987 14...
output:
44999699996
result:
ok single line: '44999699996'
Extra Test:
score: 0
Extra Test Passed