QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190908#7520. Monster Generatorucup-team087#AC ✓110ms4292kbC++147.4kb2023-09-29 15:37:492023-11-04 16:28:17

Judging History

你现在查看的是测评时间为 2023-11-04 16:28:17 的历史记录

  • [2023-11-04 18:35:58]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:110ms
  • 内存:4404kb
  • [2023-11-04 17:09:06]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:109ms
  • 内存:4388kb
  • [2023-11-04 16:34:15]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:97
  • 用时:109ms
  • 内存:4476kb
  • [2023-11-04 16:28:17]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:110ms
  • 内存:4292kb
  • [2023-09-29 15:37:49]
  • 评测
  • 测评结果:100
  • 用时:110ms
  • 内存:4316kb
  • [2023-09-29 15:37:49]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

// using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


// -first +second
namespace downup {
template <class T> bool cmp(const pair<T, T> &a, const pair<T, T> &b) {
  return (a.first <= a.second)
      ? ((b.first <= b.second) ? (a.first < b.first) : true)
      : ((b.first <= b.second) ? false : (a.second > b.second));
}
template <class T> pair<T, T> merge(const pair<T, T> &a, const pair<T, T> &b) {
  return (a.second >= b.first)
      ? make_pair(a.first, a.second - b.first + b.second)
      : make_pair(a.first - a.second + b.first, b.second);
}
}  // downup


using Int = __int128;

// floor(a / b)
Int divFloor(Int a, Int b) {
  return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}

// ceil(a / b)
Int divCeil(Int a, Int b) {
  return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}

using U = unsigned long long;


int N;
Int M;
vector<Int> A, P, B, Q;

int main() {
  for (; ~scanf("%d", &N); ) {
    M = inInt128();
    A.resize(N);
    P.resize(N);
    B.resize(N);
    Q.resize(N);
    for (int i = 0; i < N; ++i) {
      A[i] = inInt128();
      P[i] = inInt128();
      B[i] = inInt128();
      Q[i] = inInt128();
    }
    
    vector<Int> xs;
    xs.push_back(0);
    xs.push_back(M + 1);
    auto check = [&](Int a, Int p, Int b, Int q) -> void {
      if (p != q) {
        {
          const Int x0 = divCeil(a - b, q - p);
          // if (0 <= x0 && x0 <= M + 1) xs.push_back(x0);
          for (Int x = x0 - 2; x <= x0 + 2; ++x) {
            if (0 <= x && x <= M + 1) xs.push_back(x);
          }
        }
      }
    };
    for (int i = 0; i < N; ++i) {
      check(A[i], P[i], B[i], Q[i]);
    }
    for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) {
      check(A[i], P[i], A[j], P[j]);
      check(B[i], Q[i], B[j], Q[j]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
// cerr<<"xs = "<<xs<<endl;
    
    U ans = 0;
    for (int h = 0; h < (int)xs.size() - 1; ++h) {
      const Int xL = xs[h];
      const Int xR = xs[h + 1];
      
      using Entry = pair<pair<Int, Int>, int>;
      vector<Entry> es(N);
      for (int i = 0; i < N; ++i) {
        es[i] = make_pair(make_pair(A[i] + P[i] * xL, B[i] + Q[i] * xL), i);
      }
      sort(es.begin(), es.end(), [&](const Entry &e0, const Entry &e1) -> bool {
        return downup::cmp(e0.first, e1.first);
      });
      
      vector<pair<Int, Int>> ps;
      Int c = 0, r = 0;
      for (const Entry &e : es) {
        const int i = e.second;
        c -= A[i]; r -= P[i];
        ps.emplace_back(-c, -r);
        c += B[i]; r += Q[i];
      }
      for (auto &p : ps) swap(p.first, p.second);
      sort(ps.begin(), ps.end());
      for (auto &p : ps) swap(p.first, p.second);
      
      int qsLen = 0;
      vector<pair<Int, Int>> qs(ps.size());
      for (int k = 0; k < (int)ps.size(); ++k) {
        if (k + 1 < (int)ps.size() && ps[k].second == ps[k + 1].second) continue;
        const auto &p = ps[k];
        for (; qsLen >= 2; --qsLen) {
          const auto &q2 = qs[qsLen - 2];
          const auto &q1 = qs[qsLen - 1];
          if ((q2.first - q1.first) * (p.second - q1.second) < (q1.first - p.first) * (q1.second - q2.second)) {
            break;
          }
        }
        qs[qsLen++] = p;
      }
      qs.resize(qsLen);
      
      vector<Int> cut(qsLen - 1);
      for (int k = 0; k < qsLen - 1; ++k) {
        cut[k] = divCeil(qs[k].first - qs[k + 1].first, qs[k + 1].second - qs[k].second);
      }
      U sum = 0;
      for (int k = 0; k < qsLen; ++k) {
        Int x0 = xL, x1 = xR;
        if (k > 0) chmax(x0, cut[k - 1]);
        if (k < qsLen - 1) chmin(x1, cut[k]);
        if (x0 < x1) {
          sum += (U)qs[k].first * (U)(x1 - x0);
          Int t0 = x1 - x0;
          Int t1 = x0 + x1 - 1;
          (t0 % 2 == 0) ? (t0 /= 2) : (t1 /= 2);
          sum += (U)qs[k].second * (U)t0 * (U)t1;
        }
      }
      ans += sum;
#ifdef LOCAL
cerr<<"["<<xL<<", "<<xR<<"): ps = "<<ps<<", qs = "<<qs<<endl;
if(M<=1'000'000){
 Int brt=0;
 for(Int x=xL;x<xR;++x){
  Int mx=0;
  for(const auto &p:ps)chmax(mx,p.first+p.second*x);
  cerr<<x<<": "<<mx<<endl;
  brt+=mx;
 }
 if(brt!=sum)cerr<<"brt = "<<brt<<", sum = "<<sum<<endl;
 assert(brt==sum);
}
#endif
    }
    printf("%llu\n", ans);
#ifdef LOCAL
if(M<=1'000'000){
 Int brt=0;
 for(Int x=0;x<=M;++x){
  vector<pair<Int,Int>>fs(N);
  for(int i=0;i<N;++i)fs[i]=make_pair(A[i]+P[i]*x,B[i]+Q[i]*x);
  sort(fs.begin(),fs.end(),downup::cmp<Int>);
  Int mx=0;
  Int now=0;
  for(const auto&f:fs){
   now-=f.first;
   chmax(mx,-now);
   now+=f.second;
  }
  cerr<<x<<": "<<mx<<endl;
  brt+=mx;
 }
 if(brt!=ans)cerr<<"brt = "<<brt<<", ans = "<<ans<<endl;
 assert(brt==ans);
}
#endif
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3656kb

input:

3 5
3 1 5 2
4 2 1 3
1 9 100 1

output:

113

result:

ok single line: '113'

Test #2:

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

input:

3 100000000
3 1 5 2
4 2 1 3
1 9 100 1

output:

35000000549999998

result:

ok single line: '35000000549999998'

Test #3:

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

input:

10 1000000000000000000
776874380544333 197 471391764744275 33
159838820333814 107 677112662750393 41
962335658276824 48 255593531071176 11
127404116579775 209 268525254990127 34
647620110614714 76 897947476313307 13
146196843402516 221 772928712898807 39
637929916804442 2 716937021892338 15
64200226...

output:

17883317185357051350

result:

ok single line: '17883317185357051350'

Test #4:

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

input:

10 1000000000000
519946 5 967590 4
367668 9 772494 6
635694 5 932710 1
260259 2 627580 1
84994 3 52124 6
447095 4 705749 6
427312 2 977458 7
540121 1 292993 5
556831 6 321679 4
567919 4 609512 4

output:

1542003553318518337

result:

ok single line: '1542003553318518337'

Test #5:

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

input:

10 1000000000000000000
972703917532605 2 524956306619424 679
644953227221677 4 562488807303931 696
726248880302017 2 678581164692315 811
63290732871341 4 2359762326353 451
355584232678496 3 295959529542702 895
982076563374348 4 315626935294595 161
202583559712801 1 987516708328993 170
26590404960673...

output:

4582284981606185217

result:

ok single line: '4582284981606185217'

Test #6:

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

input:

10 1000000000000000000
915236950983 25 924829121702 314
142125786492 33 125091250839 71
702305171043 11 468800042449 438
449646370235 9 56198959092 472
246955215365 12 950417123809 62
646952653060 4 858914642874 441
693754630072 34 490226765023 91
273330383457 25 749838451697 371
635897703553 24 847...

output:

18304932886689493500

result:

ok single line: '18304932886689493500'

Test #7:

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

input:

100 1000000000000000000
839671173511709 107 620743247548148 134
338569457755976 9 455191878916920 157
56529874788057 33 993208347666256 99
553193266380324 120 589361808163439 126
866467572275902 19 13931460152331 210
630774124991101 56 253227140072409 133
970610042608501 106 332792633317838 252
8813...

output:

2159229278647499039

result:

ok single line: '2159229278647499039'

Test #8:

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

input:

100 1000000000000000000
926447257775795 188 535928580576730 524
773621914798781 805 607314524993852 999
433706296251306 467 260773017334982 276
627420175261216 730 936517336182015 391
944793592281860 143 916701567834795 374
985020926183290 391 155471328385744 343
158052135419112 152 37256868527793 4...

output:

845915142005167939

result:

ok single line: '845915142005167939'

Test #9:

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

input:

5 10000000
82420 1 83004 12
90974 1 5052 16
74853 1 50459 3
40080 1 8547 14
73449 1 29852 11

output:

50401135100561

result:

ok single line: '50401135100561'

Test #10:

score: 0
Accepted
time: 94ms
memory: 3900kb

input:

100 1000000000000000000
9993245793650 4 9241831921583 115
6604842581175 13 7477954917260 107
7956734211252 3 351959292590 21
8744829275263 11 1121812966924 88
4383873864556 10 7802901884633 87
2999374450961 5 7728117026444 119
2606040601922 2 9450726899416 95
463533606932 4 456141627827 113
51628088...

output:

1462626783113250968

result:

ok single line: '1462626783113250968'

Test #11:

score: 0
Accepted
time: 107ms
memory: 3912kb

input:

100 1000000000000000000
5514922686365 63 3893026500867 7
9437390653117 2 2307883657774 37
2266370593545 180 282207773345 54
7413603305531 64 6590374339957 4
2003184336714 205 3334946120451 23
8047937523313 197 6016974069987 57
49327962408 210 95380662767 50
5796501143593 219 4738100059711 11
4403864...

output:

3008948596970395169

result:

ok single line: '3008948596970395169'

Test #12:

score: 0
Accepted
time: 103ms
memory: 3880kb

input:

100 1000000000000000000
9522256146511 22 7648033142717 124
4890738110302 13 5169707386838 200
1692873223867 14 4198546120569 164
5759367352857 61 5467937093692 19
5156572753262 64 2244161860595 92
5800903619823 60 9979656907955 2
9003875069201 21 6933129430226 204
9783187462793 49 5298708535013 190
...

output:

5391002818765040268

result:

ok single line: '5391002818765040268'

Test #13:

score: 0
Accepted
time: 110ms
memory: 3780kb

input:

100 1000000000000000000
3121743641635 206 2774880557656 124
4341273709336 48 3868201748314 58
4898184402079 75 8962585631533 152
6469059809450 191 7785613783588 151
5901037828713 109 1086985069519 120
1872215875662 118 8935389074175 187
1080302564361 60 1962889993669 35
8218338957964 95 230441706635...

output:

4006532618546541597

result:

ok single line: '4006532618546541597'

Test #14:

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

input:

100 1000000000000000000
121103125248530 208 233527234872397 54
842070374171965 178 514148681666092 126
93136745067938 256 36717885771563 224
120511269258919 654 299962020993680 15
426864331284465 625 581173275854814 257
618912001992036 511 767521635123932 235
937058562049830 716 650234846124942 322
...

output:

7367765353666615058

result:

ok single line: '7367765353666615058'

Test #15:

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

input:

100 1000000000000000000
23284392897817 126 30977511034534 38
841495940790312 583 926499138731470 57
527560260544041 179 627459187144397 29
820340813703299 663 925690360693482 6
547369350978777 777 788007180251049 43
981250793921808 349 194382279990992 63
741370530598735 297 931419589514850 56
687866...

output:

7438179643288006845

result:

ok single line: '7438179643288006845'

Test #16:

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

input:

100 1000000000000000000
872423180427906 171 928660139134452 60
173464176166260 441 30242191203867 679
291627746220343 270 316446546573556 224
433904419794557 267 453622827613070 936
322487075039542 337 273582158548540 770
442190946439316 194 402704746493069 558
224382362705672 382 660906097188180 94...

output:

1676623952079872857

result:

ok single line: '1676623952079872857'

Test #17:

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

input:

100 1000000000000000000
447083504726390 41 217084089403816 104
450487653728833 43 576979382901346 56
589969051420591 8 411176483725392 60
733710648527183 60 208793807198690 80
819246579883243 5 634295240911810 19
120573670504083 31 567245341012191 97
244593463425171 8 74367118641765 87
2790961612563...

output:

3612430687325323033

result:

ok single line: '3612430687325323033'

Test #18:

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

input:

100 1000000000000000000
432410439270777 235 116344272313715 953
18833991674565 325 492411023067340 741
993487833166770 28 8834705038993 320
998878412553368 248 570799530850940 437
194089961995026 163 273965500040581 107
128666129189367 293 279847256835557 716
653181797300576 456 136293503069973 897
...

output:

12939147014964558709

result:

ok single line: '12939147014964558709'

Test #19:

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

input:

100 1000000000000000000
210114066313907 370 401244816929180 176
711657896227396 361 581112854286866 77
812417204182776 118 837215341723765 82
204282266930923 166 422636641427393 170
944666030439036 69 563942622285108 132
76718175341639 481 806791853518922 76
256410213740841 71 15055409072833 175
732...

output:

9598469605999375590

result:

ok single line: '9598469605999375590'

Test #20:

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

input:

100 1000000000000000000
182752800360801 328 547408164765978 31
557477952347166 161 753441955886985 21
514414548285144 180 993819825241906 10
757393185241412 421 294635656072618 4
29471967015767 474 745284417822919 6
187879293744454 503 379955926601373 22
630787488112518 226 998151791416706 26
312195...

output:

15132802571592726490

result:

ok single line: '15132802571592726490'

Test #21:

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

input:

100 1000000000000000000
249608 2571692352 1254347665 19271613868028
256888 7951928041 1774397545 78315915184249
150686 3237143848 1281449179 100522891111286
32617 3269902298 1554446514 109005033573806
104197 3693458716 1245405691 14792892061217
261343 2560573771 1382558981 61037905159690
180389 3689...

output:

8150417481066096321

result:

ok single line: '8150417481066096321'

Test #22:

score: 0
Accepted
time: 93ms
memory: 3788kb

input:

100 1000000000000000000
116429503963352 16 51197563628 125673
72077114688235 6 39953310726 85648
82787991723257 9 43715545842 239107
89180287090370 10 19316156881 16914
127874136211272 9 62101758469 93904
19228879359180 8 60860048430 33677
5062624378063 8 44235669549 160474
119724750396433 9 3751989...

output:

10024419831831103889

result:

ok single line: '10024419831831103889'

Test #23:

score: 0
Accepted
time: 52ms
memory: 3788kb

input:

100 1000000000000000000
341368301992 676392 6883553181605 454147861754
419533384207 472289 4864381584079 457669628636
439946663345 597450 7395704013329 511080852853
239984586557 778563 5895115820158 329798639494
925207717 565998 924703194214 525078483728
248619018009 681387 6580096993113 40458830062...

output:

1501132812111888459

result:

ok single line: '1501132812111888459'

Test #24:

score: 0
Accepted
time: 52ms
memory: 3872kb

input:

100 1000000000000000000
43290100621379 3378 16 140571635334
28725792024427 1618 6 123577603605
24301501775931 122859 9 41696076555
6101182981017 18514 32 109596530077
18994982065834 75294 14 70351371840
57894264896210 59425 26 4097772968
19373239197111 87410 8 64031483084
40316522760510 89445 29 194...

output:

18313419429006121220

result:

ok single line: '18313419429006121220'

Test #25:

score: 0
Accepted
time: 41ms
memory: 3856kb

input:

100 1000000000000000000
1307205 16 1653 10600411199
1050633 5 9101 16743373226
438143 12 14681 5130848576
1065301 16 869 15847883646
314487 15 2943 2469799712
1926674 6 14772 3995319587
1210772 2 9297 8615332037
1808552 16 8162 6460741507
1231677 13 3893 1547571481
1007488 7 13143 15132657540
670172...

output:

8343108626723003224

result:

ok single line: '8343108626723003224'

Test #26:

score: 0
Accepted
time: 45ms
memory: 3804kb

input:

100 1000000000000000000
531 14461020001 420280819852 371
734 6619803231 15772771714 44
150 3317885708 553095772544 408
754 7913726034 1642282751903 1
749 20429290075 1581239418936 239
703 7082466958 1763051866339 300
481 4037507989 74219121786 192
268 12849355098 1895809194774 245
570 31199504644 30...

output:

8636406443698548118

result:

ok single line: '8636406443698548118'

Test #27:

score: 0
Accepted
time: 6ms
memory: 3872kb

input:

100 1000000000000000000
29153 33134553762 127944669858 868872871
30132 8539146792 125982779255 2896371374
29100 11722865389 54477797800 2257957360
1167 19437411109 116482550745 2711392389
12643 13578918215 35097851120 1280673471
12140 8165540870 11384150034 2348587317
14895 15112084057 42670011555 2...

output:

4645992019419411661

result:

ok single line: '4645992019419411661'

Test #28:

score: 0
Accepted
time: 55ms
memory: 3900kb

input:

100 1000000000000000000
36778488240 44514 5305 4486108
58315500681 58865 59757 7823663
41254195906 166605 47568 7767625
65281369644 54776 49172 1939208
538371033 96307 10665 6682255
64490525720 207231 42817 6932286
60241697404 47388 64716 6585015
67621144021 40332 4476 3138009
24021786676 66705 3270...

output:

887286818540597573

result:

ok single line: '887286818540597573'

Test #29:

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

input:

100 1000000000000000000
382 12579 6279928606416 45328812111120
350 115130 4471718882146 30783964914609
472 23214 4417361000952 4561714043553
458 118987 8610828047438 36899450133900
79 38687 4226005442145 10085748532831
197 102135 2692801623664 62666422252871
202 120799 115937068277 13291973353650
57...

output:

6893014225128783876

result:

ok single line: '6893014225128783876'

Test #30:

score: 0
Accepted
time: 52ms
memory: 3832kb

input:

100 1000000000000000000
17248231829836 46180 1198310 1635908
56460852910643 7555 4091223 2057779
4527499039982 10894 604703 1683193
9023190788455 19358 1140872 2008079
1815080323269 46603 1381146 349743
20115149069682 62575 3360159 205648
70142510570263 30371 2755870 1001133
25972233211549 41407 157...

output:

9382504927203482613

result:

ok single line: '9382504927203482613'

Test #31:

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

input:

100 1000000000000000000
795271596961159 92148559084266 720313796966099 385395618782789
175254609470107 111395916689375 488176678343966 725040999753090
129886065137190 86685218131899 282895317242437 731363928379860
90861573486221 475011065448020 228162081150093 683469109293296
511606973079156 3804335...

output:

6484896036283035261

result:

ok single line: '6484896036283035261'

Test #32:

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

input:

100 1000000000000000000
685391826339741 961518849129502 253668424476360 205055570128960
605233564378256 941332665496160 282456317351148 215197963806915
635469173265998 827936936043539 661783109732634 23466669403549
554349797722823 432616634879191 801177461224867 987178642030800
51618444907309 711630...

output:

1635483640711129151

result:

ok single line: '1635483640711129151'

Test #33:

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

input:

100 1000000000000000000
689191820960180 909385606069586 787021978212029 989529001902651
921531680302726 736083968472290 963057264825530 705354927860739
141051207685750 525878706632811 997359881191407 385938154539366
17839095734017 390222204277595 330882893944506 212392781582513
591628842960869 42827...

output:

1066344809365152374

result:

ok single line: '1066344809365152374'

Test #34:

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

input:

100 1000000000000000000
657809591008203 813940268170887 320375531980466 809187879506998
237831943743611 566021791053668 722152531743881 117016498761540
646634315847325 231946052455619 376247673681605 678040895530287
481327320003387 347828847417822 939083719849936 437605847457937
53144921635998 45251...

output:

8680688530447988173

result:

ok single line: '8680688530447988173'

Test #35:

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

input:

100 1000000000000000000
591004673841563 719557586321383 863240335092536 710756663804977
173448668773633 213344937376321 84167260745661 244758915272297
263109883607901 823534006882747 30398025830621 151246279244748
161233682500185 582207775299627 617331528457632 167256737327506
922373371967710 162759...

output:

3230025435892333286

result:

ok single line: '3230025435892333286'

Test #36:

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

input:

100 1000000000000000000
551729815007224 631177315123439 500763478501020 378136890570797
940797993512037 155526544522343 197032044450853 97330426869189
657798384686829 749634934109556 977031398614127 297430749600962
408303768476592 376719751489253 998493511645692 966527372296274
19487026243087 193408...

output:

11942132701701321514

result:

ok single line: '11942132701701321514'

Test #37:

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

input:

100 1000000000000000000
520346511280655 579044072030755 34117032269458 197795768142376
221912811089498 985462219587305 842448619836403 587488464664838
128197120726805 455701206190540 391102489451332 659902234736779
836607620657130 334326394629481 606694337518354 270236905066547
559498498038471 52460...

output:

17195919289861931650

result:

ok single line: '17195919289861931650'

Test #38:

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

input:

100 1000000000000000000
516256024535147 561032545043244 671642323128822 900360366997028
989261062053311 6139219853583 912003456219227 440058902519906
601382088733348 381801059708293 372919160549079 727590238198144
83677706600768 164022742907939 874176555431791 991012146849523
726980896458744 5552543...

output:

6777688527168065092

result:

ok single line: '6777688527168065092'

Test #39:

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

input:

100 1000000000000000000
476980091958984 507837719708724 273981094481242 567741667504672
721427088444707 26816220119861 946373920513218 178951722616766
31256035610164 229405520040255 433232298541673 908958006901366
295564494230167 72215558081245 255339612328907 755098409762228
824094550734120 5859023...

output:

6908786040164103193

result:

ok single line: '6908786040164103193'

Test #40:

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

input:

100 1000000000000000000
480782234063070 377209083463016 842520094080335 387399471334427
72909576490777 856752968926647 705470261140624 669108686670591
536838070029916 970657237984663 733623624202558 201061821634111
759052718499537 994635681648992 785043971339489 93992314555796
364104948820449 995594...

output:

8021712501546218977

result:

ok single line: '8021712501546218977'

Test #41:

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

input:

100 0
480782234063070 377209083463016 842520094080335 387399471334427
72909576490777 856752968926647 705470261140624 669108686670591
536838070029916 970657237984663 733623624202558 201061821634111
759052718499537 994635681648992 785043971339489 93992314555796
364104948820449 995594556803756 71440090...

output:

5854087327556341

result:

ok single line: '5854087327556341'

Test #42:

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

input:

100 0
432410439270777 235 116344272313715 953
18833991674565 325 492411023067340 741
993487833166770 28 8834705038993 320
998878412553368 248 570799530850940 437
194089961995026 163 273965500040581 107
128666129189367 293 279847256835557 716
653181797300576 456 136293503069973 897
938046871084712 27...

output:

2435729331848673

result:

ok single line: '2435729331848673'

Test #43:

score: 0
Accepted
time: 29ms
memory: 3908kb

input:

100 1000000000000000000
33554453 524329 33554434 2097246
131075 8388634 137438953518 262165
137438953485 8589934595 87 512
1099511627852 8216 549755813947 2
33554449 68719476770 2147483661 2058
268435514 134217760 524376 8589934605
65540 8796093022263 524314 68719476765
2199023255607 64 8278 5497558...

output:

6529471465368386417

result:

ok single line: '6529471465368386417'

Test #44:

score: 0
Accepted
time: 23ms
memory: 3784kb

input:

100 1000000000000000000
65632 1099511627873 85 131148
1049 96 4294967297 8388665
1099511627798 268435486 2097209 1099511627812
134217814 16777293 8388609 94
131096 68719476762 67108948 36
17592186044426 8388696 68719476801 70368744177667
4398046511160 1073741850 8589934657 181
8796093022296 10737418...

output:

8825212310086616743

result:

ok single line: '8825212310086616743'

Test #45:

score: 0
Accepted
time: 27ms
memory: 3828kb

input:

100 1000000000000000000
8242 123 67108905 268435512
8589934651 65595 4133 34359738424
70368744177699 132 524314 32826
607 4398046511123 262211 17592186044474
17592186044508 268435495 103 62
70368744177703 1099511627843 16777309 32846
33554481 262147 524296 524329
524302 262200 262155 27
703687441776...

output:

16182118047503928612

result:

ok single line: '16182118047503928612'

Extra Test:

score: 0
Extra Test Passed