QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#782291 | #2. Boat | liaojiqing2012 | 100 ✓ | 126ms | 4460kb | C++14 | 4.5kb | 2024-11-25 19:37:30 | 2024-11-25 19:37:50 |
Judging History
answer
// Hydro submission #6741cd614db3773a6b78151c@1732534649227
// S2OJ Submission #18 @ 1705322644288
/*
* Author: Geunwoo Bae(functionx)
* Time Complexity: O(N^2 lg N)
*/
#include<stdio.h>
#include<cmath>
#include<complex>
#include<algorithm>
#include<vector>
#define mod 1000000007
using namespace std;
typedef long long lld;
typedef complex<double> base;
struct qry {
int ix;
lld x, pm;
bool operator< (const qry& c) const {
return x<c.x;
}
}que[11010];
int n, chk[5050], act, qcn;
lld dy[5050], inv[5050];
void fft(vector <base> &a, bool invert){
int n = a.size();
for(int i=1,j=0; i<n; i++){
int bit = n>>1;
for(; j>=bit; bit>>=1)j -= bit;
j += bit;
if(i<j)swap(a[i], a[j]);
}
for(int len=2; len<=n; len<<=1){
double ang = 2*M_PI/len*(invert?-1:1);
base wlen(cos(ang), sin(ang));
for(int i=0; i<n; i+=len){
base w(1);
for(int j=0; j<len/2; j++){
base u=a[i+j], v=a[i+j+len/2]*w;
a[i+j] = u+v;
a[i+j+len/2] = u-v;
w *= wlen;
}
}
}
if(invert){
for(int i=0; i<n; i++)a[i] /= n;
}
}
void convolution(vector<lld>& x, vector<lld>& y, const int sz){
vector<base> fa1, fa2, fb1, fb2;
int n, i;
for(n=1; n<sz; n<<=1);
for(i=0; i<n; i++){
fa1.push_back(0), fa2.push_back(0);
fb1.push_back(0), fb2.push_back(0);
}
for(i=0; i<sz; i++){
fa1.push_back(x[i]/30000), fa2.push_back(x[i]%30000);
fb1.push_back(y[i]/30000), fb2.push_back(y[i]%30000);
}
n<<=1;
fa1.resize(n), fa2.resize(n);
fb1.resize(n), fb2.resize(n);
fft(fa1, 0), fft(fa2, 0);
fft(fb1, 0), fft(fb2, 0);
for(i=0; i<n; i++){
base a1b1 = fa1[i]*fb1[i], a1b2 = fa1[i]*fb2[i];
base a2b1 = fa2[i]*fb1[i], a2b2 = fa2[i]*fb2[i];
fa1[i] = a1b1, fa2[i] = a1b2, fb1[i] = a2b1, fb2[i] = a2b2;
}
fft(fa1, 1), fft(fa2, 1);
fft(fb1, 1), fft(fb2, 1);
for(i=0; i<sz; i++){
lld a1b1, a1b2, a2b1, a2b2;
a1b1 = lld(fa1[i].real() + (fa1[i].real()>0 ? 0.5:-0.5)), a1b1%=mod;
a1b2 = lld(fa2[i].real() + (fa2[i].real()>0 ? 0.5:-0.5)), a1b2%=mod;
a2b1 = lld(fb1[i].real() + (fb1[i].real()>0 ? 0.5:-0.5)), a2b1%=mod;
a2b2 = lld(fb2[i].real() + (fb2[i].real()>0 ? 0.5:-0.5)), a2b2%=mod;
x[i] = (a1b1*900000000ll + (a1b2+a2b1)*30000ll + a2b2)%mod;
}
}
/*
void convolution(vector<lld>& x, vector<lld>& y, const int sz){
int i, j;
for(i=sz-1; i>=0; i--){
lld sum=0;
for(j=0; j<=i; j++){
sum+=x[j]*y[i-j];
sum%=mod;
}
x[i]=sum;
}
}*/
lld pw(lld a, lld b){
if(b<=0)return 1;
lld g=pw(a,b/2);
g=(g*g)%mod;
if(b%2)g=(g*a)%mod;
return g;
}
int main(){
int i;
lld pv;
scanf("%d", &n);
for(i=0; i<n; i++){
lld s, e;
scanf("%lld%lld", &s, &e);
que[qcn].ix=i, que[qcn].x=s, que[qcn++].pm=1;
que[qcn].ix=i, que[qcn].x=e+1, que[qcn++].pm=-1;
}
for(i=1; i<=n; i++)inv[i]=pw(i, mod-2);
sort(que, que+qcn);
pv=0;
for(i=0; i<qcn; i++){
if(pv<que[i].x && act){
lld psum=-1, sum=0, mul=1;
int j, ccn=0;
vector <lld> p, q;
for(j=0; j<n; j++){
if(chk[j]){
lld arg = sum-psum+mod;
while(arg>=mod)arg-=mod;
mul *= (que[i].x-pv+ccn)*inv[ccn+1]%mod;
mul %= mod;
p.push_back(arg);
q.push_back(mul);
psum=sum;
ccn++;
}
sum += dy[j];
if(sum >= mod)sum -= mod;
}
convolution(p, q, ccn);
for(j=ccn=0; j<n; j++){
if(chk[j]){
dy[j] += p[ccn];
if(dy[j] >= mod)dy[j] -= mod;
ccn++;
}
}
}
/* printf("%lld ~ %lld:\n", pv, que[i].x-1);
for(int j=0; j<n; j++)printf("%lld ", dy[j]);
puts("");*/
pv = que[i].x;
chk[que[i].ix] += que[i].pm, act += que[i].pm;
}
lld sum=0;
for(i=0; i<n; i++){
sum += dy[i];
if(sum >= mod)sum -= mod;
}
printf("%lld", sum);
return 0;
}
詳細信息
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 1ms
memory: 4000kb
input:
500 308810287 308810287 53564892 53564892 316377768 316377768 420249597 420249597 731165653 731165653 319087025 319087025 153776963 153776963 425464316 425464316 651047701 651047701 142502072 142502072 31632388 31632388 572337890 572337890 400220429 400220429 414382974 414382974 279400752 279400752 ...
output:
553232367
result:
ok single line: '553232367'
Test #2:
score: 9
Accepted
time: 1ms
memory: 4108kb
input:
500 259419237 259419237 71604627 71604627 140848485 140848485 45258355 45258355 417882612 417882612 70908445 70908445 647789306 647789306 269825295 269825295 528839543 528839543 35956097 35956097 555387597 555387597 114446845 114446845 663753828 663753828 236039707 236039707 730686123 730686123 1874...
output:
818775560
result:
ok single line: '818775560'
Test #3:
score: 9
Accepted
time: 1ms
memory: 4144kb
input:
500 409222683 409222683 424488829 424488829 415529128 415529128 852855991 852855991 199702963 199702963 121993369 121993369 660424994 660424994 247915283 247915283 11387254 11387254 198385312 198385312 49663799 49663799 640850062 640850062 123783577 123783577 460294327 460294327 41816505 41816505 77...
output:
676116158
result:
ok single line: '676116158'
Test #4:
score: 9
Accepted
time: 1ms
memory: 4096kb
input:
500 619714633 619714633 470637076 470637076 88903555 88903555 219610285 219610285 213164397 213164397 438259138 438259138 640791314 640791314 306721667 306721667 225421135 225421135 233222391 233222391 205820722 205820722 692168797 692168797 48417870 48417870 398991106 398991106 393107546 393107546 ...
output:
826747956
result:
ok single line: '826747956'
Test #5:
score: 9
Accepted
time: 1ms
memory: 4032kb
input:
500 781499655 781499655 32818153 32818153 128804256 128804256 106725036 106725036 373502067 373502067 522124816 522124816 327019589 327019589 28487843 28487843 242370575 242370575 340419621 340419621 156024191 156024191 293959833 293959833 651063779 651063779 185398156 185398156 23810548 23810548 15...
output:
796144690
result:
ok single line: '796144690'
Test #6:
score: 9
Accepted
time: 1ms
memory: 4148kb
input:
500 471686 471686 89197062 89197062 4486841 4486841 223318132 223318132 5382727 5382727 6119192 6119192 6920252 6920252 7400635 7400635 8953527 8953527 9453109 9453109 10297661 10297661 11088577 11088577 11747318 11747318 13120793 13120793 13620658 13620658 13858796 13858796 14388301 14388301 146049...
output:
287072213
result:
ok single line: '287072213'
Test #7:
score: 9
Accepted
time: 1ms
memory: 4288kb
input:
500 753345 753345 807697 807697 1544540 1544540 2467957 2467957 2620013 2620013 4381651 4381651 5343267 5343267 5650005 5650005 6291995 6291995 7239714 7239714 8727983 8727983 9137734 9137734 9167898 9167898 10039210 10039210 10042325 10042325 11550040 11550040 11642995 11642995 12967910 12967910 13...
output:
454779099
result:
ok single line: '454779099'
Test #8:
score: 9
Accepted
time: 1ms
memory: 4228kb
input:
500 2121408 2121408 2590977 2590977 2954510 2954510 3391039 3391039 3456654 3456654 3749072 3749072 4891660 4891660 5175214 5175214 25595893 25595893 8207147 8207147 8471111 8471111 8542387 8542387 8571053 8571053 9561645 9561645 9686851 9686851 9766228 9766228 10735337 10735337 11488198 11488198 11...
output:
794869016
result:
ok single line: '794869016'
Test #9:
score: 9
Accepted
time: 1ms
memory: 4356kb
input:
500 1067490 1067490 187728209 187728209 2331190 2331190 2402125 2402125 2635735 2635735 2952562 2952562 2996248 2996248 3434435 3434435 3506579 3506579 4727619 4727619 4948298 4948298 6100013 6100013 7237778 7237778 9714151 9714151 11703576 11703576 148126723 148126723 14940558 14940558 16312000 163...
output:
620087548
result:
ok single line: '620087548'
Test #10:
score: 9
Accepted
time: 1ms
memory: 4284kb
input:
500 2212852 2212852 2573958 2573958 3807064 3807064 4541303 4541303 4738320 4738320 5370702 5370702 5432558 5432558 371112074 371112074 8844474 8844474 8853776 8853776 9304445 9304445 11586488 11586488 12141143 12141143 12744747 12744747 15599671 15599671 15817906 15817906 146704510 146704510 163676...
output:
271082404
result:
ok single line: '271082404'
Test #11:
score: 9
Accepted
time: 1ms
memory: 4356kb
input:
500 524893 524893 2750062 2750062 3570891 3570891 4638547 4638547 4674487 4674487 4862482 4862482 5519675 5519675 9272918 9272918 9748535 9748535 9864262 9864262 10265009 10265009 15407366 15407366 16115070 16115070 16840848 16840848 17360063 17360063 17484830 17484830 17877302 17877302 19863611 198...
output:
822157788
result:
ok single line: '822157788'
Test #12:
score: 9
Accepted
time: 0ms
memory: 4288kb
input:
500 1540808 1540808 1937564 1937564 5283319 5283319 7804041 7804041 8433829 8433829 823139355 823139355 10494027 10494027 10546482 10546482 10621868 10621868 12153702 12153702 14415814 14415814 14426450 14426450 14804293 14804293 397985392 397985392 16988704 16988704 18836771 18836771 19696492 19696...
output:
455632768
result:
ok single line: '455632768'
Test #13:
score: 9
Accepted
time: 1ms
memory: 4300kb
input:
500 245210 245210 386280 386280 901085 901085 1260725 1260725 2429888 2429888 2654946 2654946 5006386 5006386 5371303 5371303 5813686 5813686 6154770 6154770 6350055 6350055 6508782 6508782 7456974 7456974 8140422 8140422 10003117 10003117 10268361 10268361 10642582 10642582 12660838 12660838 129157...
output:
902897517
result:
ok single line: '902897517'
Test #14:
score: 9
Accepted
time: 0ms
memory: 4156kb
input:
500 1114055 1114055 1562475 1562475 2053281 2053281 3495973 3495973 5137725 5137725 5658217 5658217 8216527 8216527 309196291 309196291 10687446 10687446 12153021 12153021 13249709 13249709 14657222 14657222 16140910 16140910 16171193 16171193 17460544 17460544 53076303 53076303 18954216 18954216 20...
output:
405249073
result:
ok single line: '405249073'
Test #15:
score: 9
Accepted
time: 1ms
memory: 4292kb
input:
500 1221260 1221260 1536448 1536448 1596219 1596219 3817144 3817144 5547038 5547038 5835095 5835095 8575834 8575834 13879314 13879314 13995687 13995687 14266986 14266986 16029893 16029893 16046286 16046286 16527064 16527064 35000863 35000863 18449319 18449319 18985127 18985127 19461392 19461392 1948...
output:
346378962
result:
ok single line: '346378962'
Test #16:
score: 9
Accepted
time: 0ms
memory: 4288kb
input:
500 158450518 158450518 398419544 398419544 15852367 15852367 147721606 147721606 189509271 189509271 12933510 12933510 38041970 38041970 268576530 268576530 752348312 752348312 158603479 158603479 515657574 515657574 277993122 277993122 158450518 158450518 8997617 8997617 841673344 841673344 117222...
output:
812086153
result:
ok single line: '812086153'
Test #17:
score: 9
Accepted
time: 0ms
memory: 4080kb
input:
500 557602055 557602055 181162629 181162629 632543712 632543712 666184058 666184058 682380195 682380195 553262662 553262662 632543712 632543712 635814815 635814815 229155517 229155517 208595757 208595757 472562424 472562424 714082069 714082069 728505635 728505635 321600780 321600780 109570005 109570...
output:
908497906
result:
ok single line: '908497906'
Test #18:
score: 9
Accepted
time: 1ms
memory: 4304kb
input:
500 98524121 98524121 114027386 114027386 126071599 126071599 190426100 190426100 3643106 3643106 98524121 98524121 818260656 818260656 177510656 177510656 149595703 149595703 114980573 114980573 163331808 163331808 98524121 98524121 114980573 114980573 659960023 659960023 7634737 7634737 662508335 ...
output:
456073831
result:
ok single line: '456073831'
Test #19:
score: 9
Accepted
time: 1ms
memory: 4116kb
input:
500 242086234 242086234 698376795 698376795 261877241 261877241 844564041 844564041 183035910 183035910 382328127 382328127 80253578 80253578 203346776 203346776 912382968 912382968 93064185 93064185 431774176 431774176 278790959 278790959 363084713 363084713 273437132 273437132 678641564 678641564 ...
output:
340749954
result:
ok single line: '340749954'
Test #20:
score: 9
Accepted
time: 0ms
memory: 4148kb
input:
500 96243961 96243961 558940945 558940945 262224079 262224079 535961870 535961870 518474366 518474366 96243961 96243961 783348140 783348140 181632008 181632008 584798581 584798581 173499219 173499219 52148740 52148740 2733695 2733695 2733695 2733695 284315759 284315759 643050814 643050814 457614794 ...
output:
957883219
result:
ok single line: '957883219'
Subtask #2:
score: 22
Accepted
Dependency #1:
100%
Accepted
Test #21:
score: 22
Accepted
time: 75ms
memory: 4220kb
input:
500 2425 2847 684 2839 462 1824 1522 4144 2140 3238 1750 4806 224 703 3351 5040 2882 2950 345 3747 794 2651 991 1127 639 2031 1118 2638 1264 2846 1537 2048 745 1969 4864 4903 3354 3752 1291 4991 448 4482 297 1945 4822 4929 2538 5080 1883 4299 828 4709 1273 4804 1927 4361 254 1956 832 1451 2791 2902 ...
output:
359985632
result:
ok single line: '359985632'
Test #22:
score: 22
Accepted
time: 77ms
memory: 4104kb
input:
500 339 3243 558 2133 2178 4549 807 2946 1183 1973 1338 2665 87 245 1836 3299 1541 4561 2167 5058 224 4908 1163 3638 1130 1657 882 2183 1261 4670 2180 4996 606 4329 268 1036 1623 2730 1680 2268 595 1838 304 4629 911 4274 1060 2803 3012 3714 2638 3860 1108 5077 4506 4843 2137 2370 2832 3573 1367 3217...
output:
749637311
result:
ok single line: '749637311'
Test #23:
score: 22
Accepted
time: 66ms
memory: 4148kb
input:
500 557 992 63 1129 802 5128 2764 5038 2467 2764 1923 4649 2864 3884 1601 5129 2936 4853 1412 3047 516 3107 1682 4510 3701 5039 964 4515 3562 4021 1446 2485 1026 1272 1605 4635 1154 3508 681 891 1659 2750 146 1782 858 2603 191 3115 373 1560 1495 3780 1908 5096 4664 5022 1374 1734 1596 4385 1425 4634...
output:
459759093
result:
ok single line: '459759093'
Test #24:
score: 22
Accepted
time: 74ms
memory: 4336kb
input:
500 1602 1738 3878 4429 1499 1686 426 4555 778 4804 99 1775 2139 4940 2260 5097 4388 4831 1188 3176 1769 3759 359 1658 855 4259 1763 4643 4541 4918 2610 4122 363 5173 972 2325 952 1600 1645 1991 2956 3749 2939 3497 2638 4944 472 2419 2968 4437 2829 2957 4320 4700 1119 2147 3701 4255 4662 5159 454 19...
output:
784900718
result:
ok single line: '784900718'
Test #25:
score: 22
Accepted
time: 71ms
memory: 4284kb
input:
500 817 4516 381 2523 903 5196 3618 4260 592 4313 313 1075 3688 4289 4511 4657 2000 2061 1093 4711 700 3366 1277 5086 1977 5048 146 3724 3760 4247 17 2945 757 3791 3704 4676 77 2747 1025 3585 863 4966 1590 2840 1330 2064 541 1238 265 1135 1908 4892 1138 3203 2812 4292 1146 2793 794 3829 592 2814 156...
output:
978738112
result:
ok single line: '978738112'
Test #26:
score: 22
Accepted
time: 110ms
memory: 4460kb
input:
500 1 1925 2 1925 4 1931 8 1932 12 1933 19 1934 21 1936 26 1938 28 1945 36 1950 39 1951 44 1960 47 1968 50 1968 52 1970 62 1977 69 1981 85 1990 101 1991 105 1992 110 2002 112 2002 113 2003 117 2004 130 2011 134 2016 134 2019 135 2026 137 2057 142 2065 145 2071 157 2073 165 2078 165 2078 1796 3816 17...
output:
807464304
result:
ok single line: '807464304'
Test #27:
score: 22
Accepted
time: 109ms
memory: 4240kb
input:
500 26 2087 39 2091 42 2093 501 2515 57 2096 64 2109 67 2111 71 2112 79 2120 102 2122 111 2124 113 2126 115 2128 115 2129 116 2129 116 2131 119 2141 121 2142 124 2147 130 2149 132 2150 146 2152 148 2154 160 2155 164 2160 164 2162 167 2168 167 2173 168 2173 171 2183 175 2184 176 2186 179 2191 184 219...
output:
689161857
result:
ok single line: '689161857'
Test #28:
score: 22
Accepted
time: 113ms
memory: 4240kb
input:
500 4 1905 7 1916 15 1916 18 1920 943 2914 24 1923 28 1932 37 1948 52 1950 55 1954 56 1959 57 1959 57 1964 63 1978 70 1986 72 1990 74 1991 78 1993 80 1993 81 1997 84 1997 98 2003 116 2003 117 2004 118 2005 120 2008 121 2008 122 2021 128 2028 132 2035 135 2037 138 2039 138 2040 140 2043 140 2053 142 ...
output:
360944141
result:
ok single line: '360944141'
Test #29:
score: 22
Accepted
time: 108ms
memory: 4404kb
input:
500 12 2018 1754 3604 17 2023 19 2026 19 2031 21 2053 25 2056 27 2056 29 2060 29 2069 35 2077 40 2077 44 2089 56 2091 59 2091 60 2095 520 2482 63 2099 67 2105 68 2112 72 2112 81 2123 85 2126 94 2129 105 2131 106 2134 109 2135 115 2135 118 2141 119 2143 123 2144 624 2647 131 2150 141 2151 145 2157 14...
output:
436386241
result:
ok single line: '436386241'
Test #30:
score: 22
Accepted
time: 109ms
memory: 4224kb
input:
500 1 1975 10 1979 19 1980 33 1988 34 1997 34 2002 35 2009 35 2014 36 2016 43 2022 46 2022 47 2024 52 2025 56 2035 59 2039 66 2039 70 2053 70 2053 71 2055 75 2055 79 2056 94 2066 94 2072 96 2072 98 2073 102 2078 114 2080 127 2083 128 2084 130 2093 182 2138 133 2096 135 2098 137 2107 139 2110 141 211...
output:
272725784
result:
ok single line: '272725784'
Test #31:
score: 22
Accepted
time: 0ms
memory: 3968kb
input:
500 257392824 257393039 257206183 257207501 257207498 257209286 257209284 257210501 257210495 257211281 257211277 257211437 257211436 257212063 257212055 257213546 257213545 257215050 257215046 257215525 257215517 257217466 257217457 257218493 257218491 257218680 257218679 257220636 257220633 257220...
output:
741963819
result:
ok single line: '741963819'
Test #32:
score: 22
Accepted
time: 2ms
memory: 4112kb
input:
500 359763520 359764666 359764664 359765010 359765010 359765531 359765530 359766113 359766112 359766300 359766293 359766905 359766901 359768291 359768288 359768361 359768360 359770047 359770040 359771645 359771637 359773274 359773270 359774450 359774446 359776113 359776111 359777764 359777761 359778...
output:
550172424
result:
ok single line: '550172424'
Test #33:
score: 22
Accepted
time: 2ms
memory: 4036kb
input:
500 275094475 275095639 275095639 275095814 275095811 275097717 275097710 275098688 275098685 275098842 275098835 275099017 275099014 275100677 275100674 275101376 275101375 275103362 275103357 275103826 275103821 275105549 275105547 275106688 275106686 275108603 275108596 275108905 275108900 275109...
output:
130181147
result:
ok single line: '130181147'
Test #34:
score: 22
Accepted
time: 2ms
memory: 4036kb
input:
500 339490516 339491326 339491322 339493093 339493090 339495078 339495075 339495504 339495496 339496963 339496957 339497530 339497529 339497806 339497802 339498840 339498835 339500824 339500817 339500999 339500997 339501589 339501586 339502751 339502747 339504539 339504536 339505356 339505351 339505...
output:
423772182
result:
ok single line: '423772182'
Test #35:
score: 22
Accepted
time: 2ms
memory: 4156kb
input:
500 455881331 455881991 455881983 455883495 455883495 455884407 455884400 455885135 455885132 455885654 455885647 455885931 455885930 455887113 455887111 455888483 455888480 455889114 455889111 455891127 455891127 455891500 455891497 455892238 455892237 455894107 455894102 455895008 455895003 455895...
output:
954596898
result:
ok single line: '954596898'
Test #36:
score: 22
Accepted
time: 2ms
memory: 4356kb
input:
500 23132758 23136784 22787999 22792740 22316316 22316986 22585370 22588120 23083529 23095626 22379372 22381675 22333301 22334770 22557149 22557978 22411347 22411622 22925200 22929348 22957362 22963815 22465412 22466029 22741689 22743639 22265555 22266080 22919671 22925200 22222222 22223864 22521652...
output:
201460115
result:
ok single line: '201460115'
Test #37:
score: 22
Accepted
time: 0ms
memory: 4148kb
input:
500 22302917 22303387 22837337 22841765 22597675 22597827 22577081 22577708 22861833 22867944 22687464 22689980 22758003 22759386 22556464 22559057 22307353 22309434 22770275 22771281 22559057 22560557 22481171 22483638 22441942 22441975 22524040 22526871 22335380 22336914 22958078 22960136 22947931...
output:
252371564
result:
ok single line: '252371564'
Test #38:
score: 22
Accepted
time: 2ms
memory: 4140kb
input:
500 22526726 22528592 22482585 22484632 22551295 22552329 22318130 22319190 22903057 22904176 22806707 22808570 22310072 22311440 22812916 22817121 22987822 22993227 22961336 22963437 22614312 22617178 22634398 22634756 22291096 22291182 22856257 22859271 22489368 22490312 22820599 22821364 22538217...
output:
68020425
result:
ok single line: '68020425'
Test #39:
score: 22
Accepted
time: 0ms
memory: 4284kb
input:
500 22391177 22393392 22474300 22476662 22550513 22553373 22674877 22678495 22694414 22695550 22535707 22537612 22224832 22225535 22227768 22228993 22600220 22600988 22579945 22582548 22308542 22309754 22367670 22369956 22332855 22333848 22505745 22507602 22811522 22814334 22568139 22569417 22449366...
output:
891271575
result:
ok single line: '891271575'
Test #40:
score: 22
Accepted
time: 2ms
memory: 4000kb
input:
500 22932573 22933372 23025447 23034719 22231801 22232122 22615796 22616882 22450819 22450877 22384220 22384829 22952312 22953377 22330798 22332006 22516160 22517109 22663656 22665445 23055040 23058572 22269927 22271309 22703515 22705130 22420777 22421967 22483040 22483296 22853077 22858405 22876894...
output:
802692144
result:
ok single line: '802692144'
Subtask #3:
score: 27
Accepted
Test #41:
score: 27
Accepted
time: 3ms
memory: 4100kb
input:
100 191358459 947004691 342443850 366915813 22574423 36448174 228846908 747282766 190110113 253913299 93029730 879223713 290883541 747723417 162887369 973643964 586349400 863191444 242642824 878391136 18343882 502405347 18658435 174450786 308510413 787915209 79222154 665119810 422422946 793255277 53...
output:
167281196
result:
ok single line: '167281196'
Test #42:
score: 27
Accepted
time: 3ms
memory: 4100kb
input:
100 383581393 816569935 148622782 696834692 514001933 750928139 133856778 549893268 514506767 925250706 217782864 954840051 903391822 953609501 29918251 32907029 470521732 690436226 499464782 741535745 787778349 959778964 430781962 497845242 269734667 660122499 580335811 745113176 756807722 87971325...
output:
281268921
result:
ok single line: '281268921'
Test #43:
score: 27
Accepted
time: 3ms
memory: 4280kb
input:
100 47376766 664313233 394991487 987813102 567510996 864092804 474261027 978587193 509899432 901924991 373485619 996550948 38985049 473280384 12721037 440510222 550510929 624405552 302186547 382317878 56742034 999054012 325629327 680836214 207364731 926875891 594450942 770071514 753663655 851754873 ...
output:
720025843
result:
ok single line: '720025843'
Test #44:
score: 27
Accepted
time: 3ms
memory: 4340kb
input:
100 298419616 843564930 59305155 297269005 531834796 928938169 441735148 973559139 605818424 621425326 703322783 800904117 539057263 839739855 170044757 374288196 23611398 790255887 47685709 779877820 283057492 638606328 38833997 694366776 178486963 538594252 39641281 342815660 436787994 668729197 8...
output:
826742871
result:
ok single line: '826742871'
Test #45:
score: 27
Accepted
time: 4ms
memory: 3988kb
input:
100 555348798 709755670 168305976 212781628 228849382 744856727 56990747 168240982 787296311 984214458 169406326 917964743 158730667 910083423 12190181 112640248 110033901 995322986 300818828 374776167 233036103 963819115 142239043 570131457 299911077 935341942 584668465 699560602 45776192 885937888...
output:
413352225
result:
ok single line: '413352225'
Test #46:
score: 27
Accepted
time: 5ms
memory: 4288kb
input:
100 4286365 334929271 4981537 338808196 23557681 356699543 33398390 358101339 34707941 358658676 38324357 359183774 95038043 439124352 41048045 360430437 41768720 371264235 287907515 691529451 43996090 376960454 273337618 677267192 199544359 589099362 63243951 403838291 64933918 410238579 43243549 3...
output:
44387135
result:
ok single line: '44387135'
Test #47:
score: 27
Accepted
time: 5ms
memory: 4096kb
input:
100 20024968 371243560 330351675 712369644 23278781 380556271 318072353 701674210 27372590 389713615 27686608 391001475 34068033 394316754 36509231 394786232 322674812 705258749 41512160 397511305 51856814 404987080 319088752 704784719 49917172 401779835 50075615 403955860 48661613 398682628 5406787...
output:
7399403
result:
ok single line: '7399403'
Test #48:
score: 27
Accepted
time: 5ms
memory: 4064kb
input:
100 9198943 369659170 252989538 575101349 19510121 374889661 21431381 384205475 335874543 719411028 24658942 391583394 27093001 398757268 34206074 399439383 35200850 399963001 35890489 401635559 40759287 407411585 342408092 730051987 53733306 416593228 55894064 420964533 309940688 690955410 58876958...
output:
450095995
result:
ok single line: '450095995'
Test #49:
score: 27
Accepted
time: 5ms
memory: 4100kb
input:
100 1706537 371893895 4810220 372381936 340358769 711984953 297035471 662141002 8564434 384377677 19722778 389427013 23072979 391832621 26574110 393971158 32891774 394720943 42403951 402242215 35545896 401021085 38387143 401746251 106247438 444091749 47460907 404447518 48831160 404757697 55888803 40...
output:
888369190
result:
ok single line: '888369190'
Test #50:
score: 27
Accepted
time: 5ms
memory: 4304kb
input:
100 48265690 374587600 10490181 339498659 10924429 341652033 11618636 342565709 22882930 343352180 280917927 711718056 143525633 493359100 28422578 362842787 28596159 363155050 313132775 736801779 26957300 359984482 7994339 337785020 59713146 376376490 62418047 387721020 68395789 390187577 69857186 ...
output:
639276319
result:
ok single line: '639276319'
Test #51:
score: 27
Accepted
time: 3ms
memory: 4292kb
input:
100 1742949 162238200 5430997 752445937 5803156 568237652 11057966 45859889 16561452 908042947 18085991 769134265 18336626 358689120 18795682 348214311 29825242 263584110 31772977 437320451 39282990 600273357 52063839 996154673 431097815 778404392 57718388 619194664 64482635 429954303 75271030 97973...
output:
168347538
result:
ok single line: '168347538'
Test #52:
score: 27
Accepted
time: 3ms
memory: 4344kb
input:
100 1648626 403768768 5159779 392060583 6900671 187788672 13032456 837080381 19967029 113388787 22847858 101380347 433114523 867399222 35420256 249064179 38282907 97140752 105867108 389731175 46520756 568343575 48929133 535156352 60108363 997642539 62426861 368711541 63328425 592452830 68987112 2466...
output:
837057837
result:
ok single line: '837057837'
Test #53:
score: 27
Accepted
time: 3ms
memory: 4116kb
input:
100 53206780 701552611 13840621 218491257 330624565 998078904 98973769 911024153 22946200 30809151 30492600 792406354 40153225 599727909 40822332 879404305 194847253 389278992 549204 266820571 53526336 948296016 59300922 822988813 65491195 377325445 66391645 836628006 71305961 98254149 81107245 3736...
output:
741328081
result:
ok single line: '741328081'
Test #54:
score: 27
Accepted
time: 0ms
memory: 4100kb
input:
100 19180936 742907446 30712602 726016511 115465166 974039212 38459157 639067171 803860636 849690860 39601910 254434876 42450831 456754044 93269462 775144162 96854254 824528603 97112505 879493663 109378147 415410035 111527508 375737657 134055587 662135693 117395348 395222066 119507482 207273589 1215...
output:
823390527
result:
ok single line: '823390527'
Test #55:
score: 27
Accepted
time: 3ms
memory: 3988kb
input:
100 1886273 642680910 6943573 931446211 14880352 64904283 103201125 477902958 30417827 546416691 32912079 157983903 39616607 623034286 56184085 85949067 459091897 510735743 57911294 590682791 58719158 333216740 60276280 411143700 346689031 997780767 65168037 700249153 93651140 127966867 94115121 524...
output:
362834974
result:
ok single line: '362834974'
Test #56:
score: 27
Accepted
time: 0ms
memory: 4096kb
input:
100 77671609 272592863 77671609 716914494 27023382 928910161 677153236 902303504 552323605 758630957 27023382 490658992 227579778 675744474 232777649 654222397 138358802 199004231 27023382 569163292 278927405 686537507 27023382 961069802 111671114 624392284 109815537 111671114 114800918 552323605 30...
output:
314359176
result:
ok single line: '314359176'
Test #57:
score: 27
Accepted
time: 0ms
memory: 4268kb
input:
100 192581477 989087814 299989070 611050414 92082640 929372492 119829869 323037264 244304079 849163329 440773553 704128696 884783889 989087814 991317871 996876660 440773553 691765647 405106437 813011908 636839572 708201120 432728824 874829328 179299262 874829328 776054905 923692911 195035122 5180580...
output:
512180893
result:
ok single line: '512180893'
Test #58:
score: 27
Accepted
time: 2ms
memory: 4020kb
input:
100 41487637 487367211 275195437 421488090 710727204 796623144 188296381 205905055 76552075 781934815 172638924 713853296 356278080 587428421 487367211 903535241 172317546 968527813 361033855 871754431 196327571 598825560 125634211 459115700 145591023 180881917 215745786 487367211 135265594 68641951...
output:
396562645
result:
ok single line: '396562645'
Test #59:
score: 27
Accepted
time: 2ms
memory: 4292kb
input:
100 78320887 403473171 572032610 981242610 11978066 791716543 114129022 595561934 177474817 981242610 828535510 969726696 363454560 368689441 437807247 981242610 249869343 527417142 261430050 349760196 727425346 956667128 68733386 909478454 222021776 727046685 317576170 572032610 570121960 572072206...
output:
67963454
result:
ok single line: '67963454'
Test #60:
score: 27
Accepted
time: 2ms
memory: 4100kb
input:
100 259780149 408143598 295251037 615898303 540680082 605229613 105297737 408143598 558572348 913604801 6634559 605229613 567181468 823596652 274912464 474921194 264891697 273354761 295251037 758122576 772619047 787443235 200069291 920935697 105297737 787443235 103695458 199104344 133070258 63987630...
output:
992480862
result:
ok single line: '992480862'
Subtask #4:
score: 42
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #61:
score: 42
Accepted
time: 79ms
memory: 4252kb
input:
500 851440668 951159939 387881127 613157870 93998278 492274255 664765993 836716756 659653974 895584535 204974205 468933806 277201217 636788879 240420920 932252402 8694538 511565691 148542184 636627129 556461249 682742862 815377050 944954653 400020908 520533742 394935657 511747852 305538880 367318828...
output:
186291617
result:
ok single line: '186291617'
Test #62:
score: 42
Accepted
time: 74ms
memory: 4056kb
input:
500 218084335 642361724 126684080 363862754 581542344 589281034 410530895 670487908 171917161 232709890 45382865 739549298 578032348 786521942 674698811 700215529 539895857 649401341 163326805 838051405 695545496 881038786 727379049 905692588 227287000 729002681 110282353 413085219 15609950 40569699...
output:
12136910
result:
ok single line: '12136910'
Test #63:
score: 42
Accepted
time: 73ms
memory: 4200kb
input:
500 173292182 726063470 617485005 979754208 327945446 845344742 95065426 408831073 744874146 939117895 219505883 571536702 620319424 666296797 35118587 302425814 17821378 238646320 75289908 212548335 330829350 951590236 757278455 797063227 375320631 694889235 683407001 954194749 31885996 141768367 1...
output:
901438370
result:
ok single line: '901438370'
Test #64:
score: 42
Accepted
time: 92ms
memory: 4236kb
input:
500 96959114 721679272 388873527 518209465 244499478 892522869 536026274 775212871 243713098 942194638 415141185 530074352 112746066 208006062 809692142 834717768 354932200 739031380 561431825 679783197 354413842 798621159 29520443 644553731 176257389 818953721 983452850 991376160 524960874 91560853...
output:
599796970
result:
ok single line: '599796970'
Test #65:
score: 42
Accepted
time: 74ms
memory: 4208kb
input:
500 624931439 724401192 432867185 616812682 16470026 111027857 690598502 924072970 57118760 835192562 400827375 881648975 174166533 759219895 123075470 554761723 158728073 730436727 18051057 604464751 699162356 781267467 506976027 667507283 52043812 313838158 97329290 473146815 77123728 103258407 31...
output:
406223950
result:
ok single line: '406223950'
Test #66:
score: 42
Accepted
time: 124ms
memory: 4264kb
input:
500 70275 371693882 570790 371990164 3035796 372540461 4414053 373776666 5617265 373843709 5743422 374000023 5816018 377062337 7533202 377235963 7573618 377662389 7712202 377876980 8412923 378510077 9202360 379184095 9987800 379497663 10934800 379562036 11878333 379826515 12040013 381243220 12339550...
output:
351717365
result:
ok single line: '351717365'
Test #67:
score: 42
Accepted
time: 125ms
memory: 4336kb
input:
500 729736 370767975 2231620 371149053 2288939 372469401 3404776 379076522 3564253 379911106 4367832 380018254 5321706 380177111 5646631 380369802 6375037 380642472 6520983 381143764 7452922 381783117 8341525 381940453 9400383 382203307 10404463 382391028 11283295 382633949 12419919 383307087 126970...
output:
165829629
result:
ok single line: '165829629'
Test #68:
score: 42
Accepted
time: 125ms
memory: 4244kb
input:
500 352905 379085200 600400 381084154 861491 381344549 1383462 381588470 1695002 382210349 2196650 382424183 2359343 384262001 2547556 384492456 3047577 384787507 3195854 385483336 3726435 385702222 3991456 385750092 4621417 386304483 6701448 386944380 6803787 388772607 7000191 389991241 7720992 391...
output:
137319555
result:
ok single line: '137319555'
Test #69:
score: 42
Accepted
time: 126ms
memory: 4204kb
input:
500 1675225 369557170 2836091 369750325 2869701 369838188 3380918 371071293 3425998 371091300 3428527 371478163 3791968 374752645 21809575 388454388 8404392 381087425 10112441 381524349 11146222 381962301 12011006 382271494 12558749 382346466 14194745 383200969 14414459 383649433 15196819 385113010 ...
output:
642419612
result:
ok single line: '642419612'
Test #70:
score: 42
Accepted
time: 125ms
memory: 4240kb
input:
500 245630 387992612 1806972 388203745 3634120 392194935 4649171 392745566 5694374 393322978 6586820 393592404 8380382 394326653 128580364 505701845 23299624 409761965 10591211 396025301 13220679 396254858 15111745 398073402 15607989 399055007 16339795 399420478 17984813 399420576 18918525 399492621...
output:
760895590
result:
ok single line: '760895590'
Test #71:
score: 42
Accepted
time: 72ms
memory: 4128kb
input:
500 529 992540448 618931 206150834 1061954 66232804 5839872 517219526 5983269 35505561 6557433 123404073 7180532 35755044 361984752 567254319 9892930 369520404 10555114 623151956 11148570 264446901 12185073 64628959 12700121 189335745 14301437 413041295 17074951 323942056 19024427 174278046 19495142...
output:
714815446
result:
ok single line: '714815446'
Test #72:
score: 42
Accepted
time: 73ms
memory: 4148kb
input:
500 1012923 941184633 2343835 300578559 4351415 620228740 5191655 951674812 6367279 581855217 6533694 265439082 7643222 177841418 7867609 267243613 9937318 792860976 14656861 374550331 15959413 177623543 16164294 754563727 16322252 617251881 18289598 652692237 18695989 241168030 18887196 458930570 2...
output:
148576527
result:
ok single line: '148576527'
Test #73:
score: 42
Accepted
time: 72ms
memory: 4164kb
input:
500 83005 398503494 260204 895810192 1474179 274129536 1907933 660406719 2275736 91739254 3134822 62448491 3237514 677826013 3989083 211510498 4393787 958358520 5877532 125153636 6790321 37446085 7805955 523375217 7885047 260699916 8569317 678903680 8577241 570099911 8691265 17939432 11828856 631171...
output:
673737161
result:
ok single line: '673737161'
Test #74:
score: 42
Accepted
time: 73ms
memory: 4168kb
input:
500 1003351 765901035 2673296 856874893 2886060 705226595 3790986 708617430 7314698 122624047 7553267 151870857 10447001 90507933 11319586 638807483 13421616 129902684 13999340 233636432 14719456 488281184 15760474 172626917 20970200 534719020 21713541 574031105 23323551 265402373 23386546 485754258...
output:
689919614
result:
ok single line: '689919614'
Test #75:
score: 42
Accepted
time: 73ms
memory: 4028kb
input:
500 642542 934933733 3354746 184437812 6094168 670136353 6470039 615718936 8698968 132889057 9492671 455450485 10763925 386098428 13881273 519008455 14102971 102922344 14416622 829486618 14752746 667966228 16159711 299814769 16263869 986452355 16634793 132430945 17178349 613741090 17583574 521625180...
output:
830017844
result:
ok single line: '830017844'
Test #76:
score: 42
Accepted
time: 16ms
memory: 4084kb
input:
500 205808516 451346097 470412594 696069181 420735847 812683185 352804737 555342470 291692047 356478084 425555569 689150295 205253397 628265613 94842944 408664393 511064554 892624801 341718641 642731051 145190239 852170571 137526353 511064554 145264863 842588575 551729857 682741844 451614002 6049097...
output:
698098207
result:
ok single line: '698098207'
Test #77:
score: 42
Accepted
time: 11ms
memory: 4084kb
input:
500 61836209 686625091 258482931 852176106 577825245 668325225 176164759 220687770 614762408 644237398 56346422 942407646 61836209 886308584 324428022 810186335 298835420 904082384 875977180 997115954 35172082 200854913 413767572 755155764 810186335 875859525 770455321 904082384 874074138 880601654 ...
output:
48652026
result:
ok single line: '48652026'
Test #78:
score: 42
Accepted
time: 15ms
memory: 4200kb
input:
500 457667772 855811880 232784559 507073783 4912688 950398058 588850701 675524294 500631611 810246277 154669439 288120542 507073783 961668235 684348742 949047944 795109197 949047944 135285052 455951445 154669439 855811880 4912688 833199512 461343068 800288081 500631611 787945723 128910010 897910420 ...
output:
384495356
result:
ok single line: '384495356'
Test #79:
score: 42
Accepted
time: 16ms
memory: 4140kb
input:
500 751651659 915544886 55536655 676174191 436342385 773549902 436342385 810391996 137016445 505442417 853143155 931658951 369261673 818591783 758896955 891256672 378488861 714905523 915544886 927887847 232963681 643856729 51046075 91971181 86039624 294093634 631147273 991109540 553705867 631147273 ...
output:
77540148
result:
ok single line: '77540148'
Test #80:
score: 42
Accepted
time: 18ms
memory: 4460kb
input:
500 273778462 924066200 314166350 929804773 346154110 818228013 116351414 312473009 69331993 185103093 919415954 970330396 541419351 575435933 224336780 225584174 597988619 966438415 234004937 818228013 242553583 687708218 617928809 721747265 13483230 379971710 541419351 768058518 379971710 81600728...
output:
353197380
result:
ok single line: '353197380'