QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153265 | #7078. Tower of the Sorcerer | PetroTarnavskyi | AC ✓ | 3136ms | 10080kb | C++17 | 2.7kb | 2023-08-29 19:42:04 | 2023-08-29 19:42:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int INF = 1000'000'447;
const LL LINF = 1ll * INF * INF;
const int MAX = 1 << 19;
LL t[MAX];
struct Segtree
{
int n;
void init(int nn)
{
n = 1;
while (n < nn) n *= 2;
FOR (i, 0, 2 * n) t[i] = LINF;
}
LL mn(int v, int tl, int tr, int l, int r)
{
if (l <= tl && tr <= r)
return t[v];
if (l >= tr || tl >= r)
return LINF;
int m = (tl + tr) / 2;
LL ans = LINF;
if (l < m)
ans = min(ans, mn(v * 2, tl, m, l, r));
if (r > m)
ans = min(ans, mn(v * 2 + 1, m, tr, l, r));
return ans;
}
LL mn(int l, int r)
{
return mn(1, 0, n, l, r);
}
void change(int v, int l, int r, int i, LL x)
{
if (l + 1 == r)
{
t[v] = x;
return;
}
int m = (l + r) / 2;
if (i < m)
change(v * 2, l, m, i, x);
else
change(v * 2 + 1, m, r, i, x);
t[v] = min(t[v * 2], t[v * 2 + 1]);
}
void change(int i, LL x)
{
change(1, 0, n, i, x);
}
};
const int N = 1e5 + 47;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, d;
cin >> n >> d;
Segtree st;
st.init(n + 1);
vector<PII> a(n);
int mx = d;
FOR (i, 0, n)
{
cin >> a[i].F >> a[i].S;
mx = max(mx, a[i].F);
}
a.PB({d, 0});
sort(ALL(a));
int b = lower_bound(ALL(a), MP(d, 0)) - a.begin();
n++;
vector<LL> pref(n + 1);
FOR (i, 0, n)
{
LL val = (a[i].S - 1) / mx * a[i].F;
pref[i + 1] = pref[i] + val;
}
vector<LL> dp(n, LINF);
//FOR (i, b + 1, n)
//{
// if (a[i].S <= d)
// {
// d = a[i].F;
// b = i;
// }
//}
dp[b] = pref[b];
st.change(b, pref[b] - pref[b + 1]);
VI R(N);
FOR (j, 0, N)
{
R[j] = lower_bound(ALL(a), MP(j, -1)) - a.begin();
}
FOR (i, b + 1, n)
{
int x = 1;
int l = lower_bound(ALL(a), MP(x, -1)) - a.begin();
int hp = a[i].S - 1;
while (x <= hp)
{
int k = hp / x;
LL q = LL(k) * a[i].F;
int nx = hp / k;
int r = R[nx + 1];
dp[i] = min(dp[i], pref[i] + st.mn(l, r) + q);
x = nx + 1;
l = r;
if (r >= i) break;
}
int r = n;
dp[i] = min(dp[i], pref[i] + st.mn(l, r));
st.change(i, dp[i] - pref[i + 1]);
//if (a[i].F >= a[n - 1].S && i != n - 1) i = n - 2;
}
cout << dp[n - 1] << '\n';
cerr << db(clock()) / CLOCKS_PER_SEC << '\n';
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
input:
4 1 3 2 4 4 5 6 1 6
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 59ms
memory: 6052kb
input:
5000 679 84191 46042 81916 66659 74636 72443 10252 57443 21838 54620 84896 58466 20832 29643 45949 20576 50399 51434 56472 90759 68909 94348 39459 1731 81207 17614 26465 11775 93861 24936 25017 64663 21042 37570 32903 68583 68840 58347 93849 10841 10190 77131 10595 1959 57163 59047 16066 89850 73741...
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 58ms
memory: 4164kb
input:
5000 685 67283 21828 19841 367 69908 57925 63894 10753 20139 20595 672 47788 81010 57483 53755 96758 85049 78636 94198 12795 97299 86489 57399 56590 30519 63514 92072 5714 60572 8651 25620 13514 27482 51652 88352 27272 4391 23458 43759 57471 95084 88191 53782 96875 52546 33731 95458 5643 75049 42685...
output:
60515
result:
ok single line: '60515'
Test #4:
score: 0
Accepted
time: 56ms
memory: 4148kb
input:
5000 883 57988 4889 27548 3497 47774 97848 73725 83535 43075 12741 86312 87522 98386 29435 88105 19813 50656 83340 32721 37465 84421 14671 92169 37187 33163 53370 95155 35577 63396 86337 20931 57282 80964 12797 84905 95122 7530 7623 1393 58436 9609 91063 92309 31959 37789 98189 74209 33091 64400 530...
output:
142420
result:
ok single line: '142420'
Test #5:
score: 0
Accepted
time: 58ms
memory: 4204kb
input:
5000 110 81857 71124 57698 64343 80952 96284 15190 95432 51153 64223 39943 25603 77013 72711 94708 24951 64786 9225 54307 29867 2166 9420 38155 28813 96118 90751 85381 30858 17457 43971 38450 20480 36831 31955 86436 3116 71718 45322 2141 92627 36585 66945 8885 99790 49929 5604 25126 14766 78673 4804...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 51ms
memory: 4116kb
input:
5000 852 68512 97389 60972 88659 73325 90709 87906 83485 39089 40758 25295 95321 61154 18959 19137 97232 40721 17563 3359 33010 484 29851 3964 60841 88065 81476 1622 35273 28703 97697 72577 9099 16043 92977 37261 95232 41086 16776 38139 94039 79650 24363 30987 95332 81397 67793 52508 71034 22631 725...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 81ms
memory: 4148kb
input:
5000 23 49957 100000 97978 100000 66997 100000 70406 100000 62250 100000 71093 100000 14758 100000 59859 100000 81605 100000 50139 100000 97303 100000 23626 100000 38523 100000 5028 100000 59461 100000 99559 100000 5150 100000 21343 100000 5738 100000 81487 100000 87427 100000 67101 100000 8692 1000...
output:
251733189
result:
ok single line: '251733189'
Test #8:
score: 0
Accepted
time: 52ms
memory: 4196kb
input:
5000 10 100000 64460 100000 96604 100000 64490 100000 95985 100000 52966 100000 9407 100000 2618 100000 50047 100000 37993 100000 94354 100000 47586 100000 91096 100000 18738 100000 88600 100000 37646 100000 88124 100000 43502 100000 56950 100000 81193 100000 14352 100000 54736 100000 14837 100000 1...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 75ms
memory: 4156kb
input:
5000 51 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 10000...
output:
196000000
result:
ok single line: '196000000'
Test #10:
score: 0
Accepted
time: 9ms
memory: 4176kb
input:
5000 2 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 24...
output:
11807600
result:
ok single line: '11807600'
Test #11:
score: 0
Accepted
time: 3ms
memory: 4328kb
input:
5000 11 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 10...
output:
45450000
result:
ok single line: '45450000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 1 1 100000 100000 1
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
2 1 1 3 3 100
output:
297
result:
ok single line: '297'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
100 178 157 16066 189 16201 134 18255 190 12359 142 15665 192 17956 120 14861 194 18445 169 13814 190 10523 198 11396 188 13529 164 16559 138 13158 154 13246 123 12920 190 19092 181 19819 147 18071 188 11408 134 17172 148 14664 192 17871 143 18116 109 19693 179 12343 180 17090 150 12711 200 19798 17...
output:
1168450
result:
ok single line: '1168450'
Test #15:
score: 0
Accepted
time: 2ms
memory: 4076kb
input:
100 9236 7864 75108 8699 16535 376 50738 5639 97958 1784 75293 9729 88266 8655 81610 9938 74490 8566 17220 9666 21635 8362 43274 1995 15239 3613 63840 8632 64439 2242 12081 3354 13214 2507 81554 7578 31837 9960 13140 1185 18627 8361 27567 3592 45065 5251 40472 9311 31355 5034 65035 5613 74538 6905 2...
output:
2511795
result:
ok single line: '2511795'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3792kb
input:
100 4368 5639 95168 7156 47518 8137 57053 1704 48642 3005 91592 7450 64182 3425 38836 5516 77818 7703 67882 8744 42240 1318 42471 6684 39471 5381 43548 1742 67073 1030 70989 2157 15781 3176 51219 6351 36894 4604 5818 9460 39265 5931 90339 7116 37275 8648 16323 9825 10441 8072 42787 9503 68159 7434 9...
output:
2538739
result:
ok single line: '2538739'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3920kb
input:
100 259 80 62302 302 57717 193 13269 771 58062 219 26436 554 22639 108 77948 970 89532 447 19679 760 97544 48 44667 211 94414 610 96029 527 37537 17 61669 995 86153 168 57342 987 11576 693 20776 174 55470 168 71708 681 10275 432 22361 106 80512 853 31365 845 57897 207 37804 107 15058 662 26829 30 57...
output:
2565739
result:
ok single line: '2565739'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4068kb
input:
100 94765 44791 9234 39635 44708 39512 84352 32154 66011 95490 38673 69605 76862 27992 84300 90563 32269 13845 16554 22423 62907 50980 71481 21655 7696 96806 72538 12431 84328 93712 11554 44475 91283 7050 94813 29168 64499 24721 33319 80563 34144 28949 60657 3264 38471 86940 51106 26629 76327 87933 ...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
1000 195 187 11608 136 14918 135 15113 159 11782 159 13355 151 14945 103 14301 153 11918 187 15797 159 15577 175 16979 178 15105 132 17688 160 11025 145 13008 176 14603 166 15739 116 18242 194 19461 117 18584 104 19047 142 12937 128 14092 158 15208 146 12487 197 17821 138 19564 150 11753 142 18718 1...
output:
11220118
result:
ok single line: '11220118'
Test #20:
score: 0
Accepted
time: 5ms
memory: 3952kb
input:
1000 3689 2418 25992 2569 90297 1939 65017 2894 50479 3342 93448 601 95293 126 34177 2683 14222 3692 55360 4435 70569 2233 15930 2285 94214 1696 48218 2605 18093 264 70767 2177 87976 3069 38238 3128 13627 2069 95572 664 31911 1153 38299 2847 18232 663 94897 526 61842 3458 36552 1804 43399 3010 18977...
output:
26297784
result:
ok single line: '26297784'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3992kb
input:
1000 3308 1336 99208 2118 65085 1307 44413 602 84005 4354 55223 721 54826 3699 58727 1247 99323 4329 93508 2854 69922 3612 84741 4387 35136 3016 74005 807 37010 2316 82232 2184 97191 4810 33549 2994 67161 3423 89070 3359 21907 2994 90806 4974 84031 3994 66716 2170 62740 1393 77560 4841 54589 2048 49...
output:
27618897
result:
ok single line: '27618897'
Test #22:
score: 0
Accepted
time: 4ms
memory: 3908kb
input:
1000 5690 5272 18563 2208 13185 9929 714 6120 93411 4027 65417 3274 6417 1557 15728 6169 20252 7863 64435 9467 7163 6526 52042 8295 47015 2836 21585 2188 76447 7822 43273 4361 76646 3978 12213 8282 55488 1772 69598 1097 68665 4831 22992 2052 25566 6487 25818 5874 87873 6847 87090 6630 15385 3127 178...
output:
25274270
result:
ok single line: '25274270'
Test #23:
score: 0
Accepted
time: 6ms
memory: 3820kb
input:
1000 613 622 12278 294 36627 327 50583 79 54719 527 64809 242 20366 611 71052 924 86998 685 68548 586 42802 289 60911 299 23970 761 69745 362 21439 354 57080 205 25072 197 73906 601 17218 511 26906 699 69989 777 51114 128 20489 848 21377 486 17410 582 61455 649 53973 423 62451 55 44187 854 75577 444...
output:
26928349
result:
ok single line: '26928349'
Test #24:
score: 0
Accepted
time: 3ms
memory: 3952kb
input:
1000 9061 4223 28214 1308 25048 2247 9513 5616 51812 1155 29478 6145 51360 1187 96078 6523 91752 9627 68567 2715 5130 9317 88298 9572 94956 2317 16166 4076 28740 7715 1500 2191 62367 9053 31921 4699 12987 3378 52095 6867 7340 8256 79347 4317 96091 1446 22865 1124 34274 5819 7116 3126 49745 2837 9431...
output:
22397306
result:
ok single line: '22397306'
Test #25:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
1000 93761 13042 45072 30325 40700 72475 32486 18918 54911 83363 66278 43430 12654 35635 60291 67455 81519 88983 64792 18976 18541 26303 98722 20826 7192 4350 6177 47363 92867 3086 45596 49463 11493 59403 42842 47058 13305 43315 63433 68535 28670 1452 50266 60108 4919 75230 80419 11932 85707 73877 1...
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 28ms
memory: 8592kb
input:
100000 1 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 1...
output:
9999900000
result:
ok single line: '9999900000'
Test #27:
score: 0
Accepted
time: 1733ms
memory: 9456kb
input:
100000 5366 6038 69255 8540 48771 2631 16671 2625 88929 8795 19689 8448 52309 6055 95769 5753 72461 3730 59096 59 70102 2184 36567 2254 69073 4872 93717 4346 25005 9926 64985 9678 50911 9273 82452 970 86394 7054 58076 4149 79485 4403 39607 9687 39308 7645 22272 7968 62643 147 30008 1376 88513 1392 6...
output:
2495521379
result:
ok single line: '2495521379'
Test #28:
score: 0
Accepted
time: 305ms
memory: 8796kb
input:
100000 9162 3148 54400 9181 29282 1661 97797 4031 30927 2169 30632 9412 87441 4643 41590 6022 25087 1247 63915 3077 73152 3736 45532 5477 92817 5323 20495 9038 9538 1354 32542 8571 96409 4491 5912 892 40717 5287 53600 9892 51820 2235 99724 2715 95797 2730 5447 156 62207 5288 20143 8520 43505 6785 62...
output:
2252325798
result:
ok single line: '2252325798'
Test #29:
score: 0
Accepted
time: 2536ms
memory: 9680kb
input:
100000 413 62258 91519 77692 62992 19764 26696 70685 57191 44108 80949 78663 87882 87439 72112 89312 40742 16407 32647 38420 30443 99936 3693 41649 13102 73452 79096 45931 7205 22880 82177 79577 10382 12005 19399 66870 86632 49448 55500 89601 75319 12538 62070 85405 34980 87536 43183 60850 48987 408...
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 37ms
memory: 8924kb
input:
100000 197 159 16368 100 10619 106 15521 103 11334 176 14602 200 18010 199 16873 182 15955 181 13568 172 11421 145 16950 124 12861 122 19502 161 16840 185 18800 173 10792 184 10986 197 17229 182 14548 100 10461 166 12290 120 12164 116 17035 117 16267 152 15607 193 12663 143 15273 138 18904 182 10050...
output:
1116803442
result:
ok single line: '1116803442'
Test #31:
score: 0
Accepted
time: 976ms
memory: 8844kb
input:
100000 3859 4649 87809 1455 83124 2284 69307 1946 69796 4079 87056 4973 89936 2404 84729 4479 88825 2649 80269 1761 57798 2548 96884 4737 86626 3337 97219 1163 67127 3617 80139 2006 75798 658 56431 4414 74582 1170 62616 2296 65879 1912 66496 1767 79378 1772 63468 1092 60832 682 81539 4772 98155 3447...
output:
3703465469
result:
ok single line: '3703465469'
Test #32:
score: 0
Accepted
time: 675ms
memory: 9468kb
input:
100000 2754 2907 87567 1201 71345 3299 55204 4076 59219 4159 53409 4836 97458 1239 70072 3563 93313 1791 52735 2181 94352 2074 72161 2686 75190 4454 91989 1794 88056 3509 83003 3096 90944 2817 83086 1092 51597 3322 91495 4302 93333 1203 98575 3189 98489 4441 78134 4515 78280 1216 63470 2723 94238 29...
output:
4355475875
result:
ok single line: '4355475875'
Test #33:
score: 0
Accepted
time: 316ms
memory: 9244kb
input:
100000 7132 9531 33225 9306 27770 1962 52481 6227 54156 5154 650 5813 90925 6151 70289 3505 47676 2764 26983 2709 23900 7052 29761 5922 91925 6916 20153 7987 4753 3754 6091 1140 29248 9468 32025 3538 28916 2289 14856 1941 79750 4950 48289 6956 5167 1535 74737 2561 30640 7292 82985 9055 61515 2128 58...
output:
2470997022
result:
ok single line: '2470997022'
Test #34:
score: 0
Accepted
time: 1886ms
memory: 8028kb
input:
100000 171 469 23603 394 78629 915 29373 904 63889 500 19635 884 84052 987 69429 460 45796 787 60687 724 46478 189 70890 767 99228 309 42789 696 89808 474 75431 981 56728 465 54615 914 86212 852 81795 576 24440 973 88191 419 37358 543 58921 797 40546 932 81176 929 43645 704 80888 647 98649 994 12567...
output:
2989584437
result:
ok single line: '2989584437'
Test #35:
score: 0
Accepted
time: 2341ms
memory: 8412kb
input:
100000 300 416 11319 1803 13825 1629 3058 950 94097 1614 90693 1272 93262 966 8953 1378 71183 1622 94797 367 76314 1237 34293 892 55182 693 12727 282 64314 1808 91948 1322 5059 738 11685 266 82658 1329 68228 187 74564 1033 98654 1550 73576 675 44096 1440 21892 1882 49671 1820 74625 441 84550 1103 19...
output:
2566613627
result:
ok single line: '2566613627'
Test #36:
score: 0
Accepted
time: 31ms
memory: 9832kb
input:
100000 1984 777 83581 1862 89453 714 7870 1698 55799 1979 16598 751 68163 1878 93735 1447 40638 1438 91403 1097 24812 1735 95791 1860 43748 1315 99955 996 11599 1769 33675 1384 63053 1459 28545 964 65935 1320 22384 1715 96286 674 60682 1732 62867 948 34868 1130 12221 1073 21765 691 63102 1072 69674 ...
output:
3065972699
result:
ok single line: '3065972699'
Test #37:
score: 0
Accepted
time: 490ms
memory: 8588kb
input:
100000 1077 1193 50551 1392 999 1075 91049 1443 86982 1031 65494 1753 8905 1067 11883 1185 47298 1505 81626 1189 91139 1174 35770 1032 75846 1351 57220 1234 36614 1883 31960 1907 61060 1338 50262 1681 72483 1005 83974 1017 72907 1301 54192 1291 35306 1297 24965 1197 57166 1408 88084 1775 90636 1476 ...
output:
3673470839
result:
ok single line: '3673470839'
Test #38:
score: 0
Accepted
time: 297ms
memory: 8284kb
input:
100000 1138 260 2486 781 2390 1635 8533 1532 6497 1448 8064 1536 405 365 8625 1133 9676 820 9477 1386 9143 1903 174 1673 6329 1603 6800 1079 8903 368 9780 436 7358 1612 1783 1636 61 606 620 163 3590 550 4038 1001 898 1818 7807 1694 6842 569 7285 1559 4478 879 3751 1304 9602 1386 476 1445 4172 1499 7...
output:
209690519
result:
ok single line: '209690519'
Test #39:
score: 0
Accepted
time: 291ms
memory: 10080kb
input:
100000 1431 1392 10443 1475 11682 894 29436 795 20635 1236 11619 1812 4857 1077 25197 505 3002 616 13692 1019 16465 1044 34467 1889 23094 711 25229 755 5331 707 20967 1985 41640 1837 30386 1288 33351 698 3186 1233 28280 1069 33985 1782 13703 1550 5628 1184 26689 915 15893 1147 10971 766 10735 1063 7...
output:
1496066026
result:
ok single line: '1496066026'
Test #40:
score: 0
Accepted
time: 1010ms
memory: 8040kb
input:
100000 579 1994 12440 1191 12117 111 13146 1286 14817 1289 10501 1516 13489 966 15819 478 17389 1855 11489 1829 18938 1585 18989 147 16362 1817 17819 1177 15591 267 15367 117 16136 813 18830 1079 11152 435 12656 1013 18163 351 12875 1800 10670 1983 16923 1844 13209 1830 11083 1229 12688 465 10184 19...
output:
737690029
result:
ok single line: '737690029'
Test #41:
score: 0
Accepted
time: 137ms
memory: 8392kb
input:
100000 1637 780 19924 1530 13482 1355 18046 1182 10985 935 11544 664 13059 1903 18817 1345 19154 1219 18270 787 13141 1532 18336 1333 17137 1519 13324 1316 16611 742 18774 1713 15332 635 18808 642 18639 785 11290 902 15639 1913 16882 997 10784 1004 19714 743 19602 1490 18247 1960 13675 1652 16131 96...
output:
875973503
result:
ok single line: '875973503'
Test #42:
score: 0
Accepted
time: 368ms
memory: 8088kb
input:
100000 14 30 98196 41 11637 72 99937 31 29504 96 57779 87 54509 83 74049 37 93645 91 92138 82 37028 39 64493 91 67377 60 26417 35 54741 28 79302 83 62372 79 70858 25 88547 16 63563 45 81466 91 12414 46 91945 89 64038 11 84651 20 68763 24 37020 87 56328 77 58939 17 40379 35 84462 74 38456 82 47747 50...
output:
3030239207
result:
ok single line: '3030239207'
Test #43:
score: 0
Accepted
time: 184ms
memory: 8076kb
input:
100000 467 143 18391 471 22687 231 21806 383 94823 362 46527 451 88115 320 89601 360 92308 383 46466 349 95722 270 60335 126 36990 113 68071 355 58054 203 30398 394 36124 117 17117 269 29509 474 36595 201 70286 167 16541 495 63496 242 75553 235 39044 251 14389 212 10259 351 89496 439 83002 407 26598...
output:
3280331792
result:
ok single line: '3280331792'
Test #44:
score: 0
Accepted
time: 666ms
memory: 8472kb
input:
100000 807 93 37772 697 6428 54 79802 63 70340 768 26414 846 62975 831 31239 260 79562 588 76037 980 61059 860 31552 596 72368 16 62714 168 90817 467 85639 637 25933 239 18782 167 95748 976 80220 659 57835 479 87249 173 29626 864 24676 604 87580 620 77072 241 70459 832 19017 444 61848 325 55889 103 ...
output:
2507577679
result:
ok single line: '2507577679'
Test #45:
score: 0
Accepted
time: 503ms
memory: 9120kb
input:
100000 8603 6807 64172 6688 36616 1288 83080 6713 41220 3546 82426 6960 84171 5732 42734 2389 6745 3471 49441 5180 35727 5658 51888 6367 2124 9289 79096 393 85090 2386 96074 1484 19731 574 98310 9597 58095 9886 12840 5315 32088 1796 17743 9051 98037 2709 9576 3143 1136 4126 93265 9466 45632 4572 401...
output:
2262610643
result:
ok single line: '2262610643'
Test #46:
score: 0
Accepted
time: 2618ms
memory: 9580kb
input:
100000 2485 40357 88472 6643 60386 99285 70965 38756 72126 30751 37879 99757 60186 9346 99560 94017 61365 19073 37307 66259 76312 73764 46265 60383 89749 66357 74679 63168 24842 8228 77181 47191 80694 89444 60946 32427 33738 10955 63403 4451 68868 87094 24155 20302 28091 18338 90208 96219 19193 2504...
output:
31035
result:
ok single line: '31035'
Test #47:
score: 0
Accepted
time: 1826ms
memory: 8988kb
input:
100000 449 121 61674 331 90298 696 77406 156 54152 822 71322 943 97327 190 53972 594 85860 959 51258 957 65394 436 55671 218 50617 973 64040 1000 52747 467 94349 603 60666 847 94403 681 53004 826 69224 430 86702 603 59083 126 85014 833 72278 618 85812 356 84879 637 90518 139 79950 890 87682 929 9326...
output:
4099888809
result:
ok single line: '4099888809'
Test #48:
score: 0
Accepted
time: 2067ms
memory: 9352kb
input:
100000 962 1922 82159 1172 65961 330 72951 916 85257 1084 65186 1694 72909 1814 78576 1736 77301 756 75425 1039 56624 580 56673 1969 97592 733 69136 1439 95827 1313 73882 1594 62465 280 76081 1006 78748 537 71007 342 59695 1398 79066 536 88491 798 64446 156 86674 394 54393 1584 84342 477 52488 760 8...
output:
3882093262
result:
ok single line: '3882093262'
Test #49:
score: 0
Accepted
time: 399ms
memory: 8032kb
input:
100000 42421 24251 31124 2844 62655 37641 1407 26595 3336 5548 84655 19994 38925 34016 60170 14966 58743 29028 3874 48083 45926 18403 11596 29705 47212 10621 5466 23602 51973 27763 98743 13474 7931 25956 53503 7048 27664 42470 95736 32104 1201 14760 62691 48607 87513 26971 63366 45902 23903 6126 679...
output:
1261460150
result:
ok single line: '1261460150'
Test #50:
score: 0
Accepted
time: 3136ms
memory: 9100kb
input:
100000 1785 9350 84598 1278 90260 5082 88623 4259 71511 8955 88184 1353 57952 6877 83911 2945 53648 5297 85512 5266 94069 1565 64104 9210 54058 7454 71590 443 79611 5033 88577 5178 81828 3445 62069 1018 92594 581 62731 8617 76908 3165 75319 6057 86114 2219 84965 1735 63021 2481 71439 348 79152 4737 ...
output:
3543585666
result:
ok single line: '3543585666'
Test #51:
score: 0
Accepted
time: 177ms
memory: 8692kb
input:
100000 878 1795 7620 1120 6852 552 4302 1934 3469 757 2746 1874 7885 986 515 1557 5522 1585 1801 1743 3324 1529 6335 1808 8913 1713 9468 1210 6938 1648 1403 671 2116 1085 1467 1829 4401 1409 399 594 836 1905 9614 904 6457 641 2756 1939 1530 1768 944 1665 6283 774 2884 1228 9647 1069 4008 1126 9504 1...
output:
250073044
result:
ok single line: '250073044'
Test #52:
score: 0
Accepted
time: 973ms
memory: 9120kb
input:
100000 708 714 100000 1151 100000 1693 100000 1380 100000 868 100000 580 100000 975 100000 1587 100000 578 100000 1595 100000 1750 100000 942 100000 1870 100000 928 100000 1490 100000 1151 100000 1937 100000 521 100000 1306 100000 997 100000 1048 100000 1431 100000 1503 100000 1129 100000 1731 10000...
output:
6123919725
result:
ok single line: '6123919725'
Test #53:
score: 0
Accepted
time: 202ms
memory: 8036kb
input:
100000 71 69 45507 83 3132 55 92929 22 71365 100 94282 41 53181 3 87761 79 42968 71 35304 100 92622 9 30171 44 89918 31 73377 22 45123 14 68713 65 83905 77 21039 6 9007 3 84041 20 8698 70 67977 26 2714 94 1962 81 68223 70 49866 84 98476 68 82880 62 76877 24 49152 55 33506 28 96221 71 6737 51 16290 7...
output:
2524559429
result:
ok single line: '2524559429'
Test #54:
score: 0
Accepted
time: 2330ms
memory: 8776kb
input:
100000 126 365 20005 394 39922 240 86273 655 81338 790 59150 574 54823 728 83093 444 66952 540 37432 1 34971 260 47835 912 30981 680 86314 995 11917 344 84447 390 29542 754 13345 928 41745 874 23226 53 66560 685 59487 382 14787 509 67430 470 40578 672 96035 831 24564 345 54011 780 46383 678 71966 26...
output:
2728088417
result:
ok single line: '2728088417'
Test #55:
score: 0
Accepted
time: 2503ms
memory: 9732kb
input:
100000 1782 1395 71576 4857 75620 2410 68200 627 76003 3472 19867 758 28321 2618 87466 1289 48608 2672 53209 3477 70756 1614 15676 1201 10607 2948 73345 31 35717 2263 38125 3148 64663 4541 14743 4563 85029 3245 55591 4403 87500 1557 12748 2941 12391 2970 16703 3159 68649 820 96402 2931 26111 3670 75...
output:
2627578502
result:
ok single line: '2627578502'
Test #56:
score: 0
Accepted
time: 2299ms
memory: 9304kb
input:
100000 9325 40503 28958 21442 85627 24585 21142 41547 30339 13872 35471 35317 96432 9543 69853 8100 86144 37599 80522 29683 3367 39530 4594 24271 1610 41185 21574 40458 22821 32832 90345 27194 4134 12485 470 35047 12495 2756 84983 27152 77304 6661 92911 34743 87338 32020 40402 43632 24901 42913 2221...
output:
1239408620
result:
ok single line: '1239408620'
Test #57:
score: 0
Accepted
time: 629ms
memory: 9364kb
input:
100000 39923 34107 87026 44168 49801 4739 55643 34327 81768 30508 59566 39157 97598 28134 80247 15208 84539 10336 40924 5854 25928 6386 95231 28116 76587 19396 90362 48927 48345 31652 14472 14967 35249 7621 49294 35735 86353 31210 58352 15871 61626 36431 77133 21682 11710 1121 84476 48296 54215 3075...
output:
1382901700
result:
ok single line: '1382901700'
Test #58:
score: 0
Accepted
time: 276ms
memory: 9012kb
input:
100000 46519 20424 67993 13494 62280 11905 70703 34688 83030 10184 73653 28431 92035 35614 62908 9802 72443 16181 58249 26690 91413 566 94142 11173 84338 27389 65808 28492 64570 29688 71387 19294 93683 32379 74229 48522 94175 11358 91545 32946 61982 40973 75851 11850 91474 29384 97928 45949 59156 19...
output:
2498783034
result:
ok single line: '2498783034'
Test #59:
score: 0
Accepted
time: 853ms
memory: 8444kb
input:
100000 34800 9933 100000 31563 100000 2198 100000 1527 100000 38156 100000 25436 100000 17688 100000 5027 100000 21124 100000 26857 100000 27967 100000 5231 100000 31980 100000 7883 100000 25874 100000 34197 100000 25293 100000 39595 100000 41211 100000 40349 100000 40289 100000 47777 100000 41220 1...
output:
2505329659
result:
ok single line: '2505329659'
Test #60:
score: 0
Accepted
time: 1048ms
memory: 8548kb
input:
100000 6501 1538 99468 3940 67286 8224 10951 1315 4666 514 6759 9056 95255 1910 91513 3855 20534 5764 18850 356 33429 2481 82650 8520 88999 5509 40428 7962 88559 5925 43704 1011 40457 6211 66322 3441 28162 4481 87456 5973 20507 2439 99583 8362 89097 2646 25374 9634 6840 4614 53921 1213 78276 7600 61...
output:
2279598856
result:
ok single line: '2279598856'
Test #61:
score: 0
Accepted
time: 266ms
memory: 9264kb
input:
100000 41463 26788 71868 52532 55506 28889 41879 19498 90728 64413 17667 41663 42342 46442 45046 25655 84034 70086 40391 16240 91189 68319 36338 95433 57470 63523 30136 59272 33823 46416 79676 48512 61918 89427 40006 81168 83206 34860 47908 42280 58723 50291 38756 84817 60682 27550 44156 47999 49774...
output:
0
result:
ok single line: '0'
Test #62:
score: 0
Accepted
time: 10ms
memory: 3912kb
input:
1000 1 55725 56643 66764 67975 27701 27214 99831 99840 53750 53991 8508 10335 20030 20723 92983 91472 20398 21235 90848 89079 35601 34001 65119 66074 96142 95385 70410 71831 26540 26306 7146 8743 49174 49954 47933 48524 46693 46657 35522 33997 92693 90988 48218 48652 32976 31634 11452 12068 26625 26...
output:
309995
result:
ok single line: '309995'
Test #63:
score: 0
Accepted
time: 123ms
memory: 4324kb
input:
10000 1 14322 14663 29459 30573 89007 88771 73561 74580 71019 72260 15629 15921 34808 35528 69540 70799 98516 98463 66383 67258 22779 23729 68783 69960 40737 41905 29278 30430 41795 42736 7051 6860 89321 89178 16391 16573 51717 52390 25003 25868 73789 74712 48039 48897 55674 56012 96032 96328 94468 ...
output:
198712
result:
ok single line: '198712'
Test #64:
score: 0
Accepted
time: 1886ms
memory: 8188kb
input:
100000 1 36859 36859 88347 88347 59933 59933 45580 45580 12030 12030 80634 80634 21589 21589 62979 62979 76057 76057 58702 58702 55552 55552 37091 37091 92843 92843 94255 94255 77430 77430 49176 49176 73965 73965 81888 81888 94229 94229 7171 7171 59659 59659 44234 44234 95998 95998 22285 22285 98344...
output:
200005
result:
ok single line: '200005'
Test #65:
score: 0
Accepted
time: 1873ms
memory: 7916kb
input:
100000 10 97710 97710 5988 5988 51602 51602 16298 16298 64202 64202 71992 71992 36783 36783 17337 17337 39723 39723 85016 85016 67336 67336 81734 81734 31802 31802 24389 24389 83013 83013 32845 32845 60646 60646 53468 53468 46932 46932 90479 90479 30749 30749 41395 41395 34022 34022 49460 49460 8135...
output:
199992
result:
ok single line: '199992'
Test #66:
score: 0
Accepted
time: 1863ms
memory: 9296kb
input:
100000 100 87747 87747 30645 30645 63212 63212 2616 2616 62294 62294 80529 80529 18276 18276 50076 50076 24624 24624 97386 97386 69744 69744 99152 99152 32271 32271 98019 98019 77360 77360 49700 49700 11744 11744 79983 79983 43917 43917 1323 1323 43275 43275 62353 62353 65650 65650 27994 27994 17373...
output:
199807
result:
ok single line: '199807'
Test #67:
score: 0
Accepted
time: 1872ms
memory: 9384kb
input:
100000 1000 26706 26706 78357 78357 4678 4678 95682 95682 59529 59529 14129 14129 35488 35488 3628 3628 77754 77754 94610 94610 90372 90372 42935 42935 61807 61807 49618 49618 27544 27544 32928 32928 91065 91065 65335 65335 24811 24811 40122 40122 61137 61137 28661 28661 35054 35054 23926 23926 9043...
output:
198438
result:
ok single line: '198438'
Test #68:
score: 0
Accepted
time: 1794ms
memory: 8888kb
input:
100000 10000 37327 37327 42348 42348 84853 84853 98283 98283 62194 62194 46047 46047 43160 43160 53495 53495 66801 66801 45618 45618 96007 96007 26923 26923 28846 28846 11511 11511 38596 38596 49724 49724 9245 9245 51830 51830 39618 39618 9772 9772 63208 63208 2551 2551 61161 61161 60695 60695 37597...
output:
187500
result:
ok single line: '187500'
Test #69:
score: 0
Accepted
time: 15ms
memory: 8044kb
input:
100000 100000 13761 13761 93673 93673 31753 31753 8576 8576 726 726 58402 58402 86853 86853 69410 69410 78127 78127 7064 7064 49156 49156 44044 44044 58356 58356 27054 27054 69840 69840 3998 3998 23764 23764 71608 71608 22027 22027 39578 39578 31879 31879 77173 77173 55271 55271 99686 99686 31279 31...
output:
0
result:
ok single line: '0'