QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388465 | #8548. China Convex Polygon Contest | ucup-team112# | AC ✓ | 94ms | 19832kb | C++23 | 14.2kb | 2024-04-13 15:59:34 | 2024-04-13 15:59:34 |
Judging History
answer
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define INTERACTIVE
namespace templates {
// type
using ll = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on
// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)
// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on
// const value
const ll MOD1 = 1000000007;
const ll MOD9 = 998244353;
const double PI = acos(-1);
// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)
// function
vector<char> stoc(string &S) {
int n = S.size();
vector<char> ret(n);
for (int i = 0; i < n; i++) ret[i] = S[i];
return ret;
}
string ctos(vector<char> &S) {
int n = S.size();
string ret = "";
for (int i = 0; i < n; i++) ret += S[i];
return ret;
}
template <class T>
auto min(const T &a) {
return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
auto b = clamp(a, l, r);
return (a != b ? a = b, 1 : 0);
}
template <typename T>
T sum(vector<T> &A) {
T tot = 0;
for (auto a : A) tot += a;
return tot;
}
template <typename T>
vector<T> compression(vector<T> X) {
sort(all(X));
X.erase(unique(all(X)), X.end());
return X;
}
// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
for (auto &a : A) is >> a;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
for (size_t i = 0; i < A.size(); i++) {
os << A[i];
if (i != A.size() - 1) os << ' ';
}
return os;
}
// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
for (auto &a : A) is >> a;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
for (size_t i = 0; i < A.size(); i++) {
os << A[i];
if (i != A.size() - 1) os << endl;
}
return os;
}
// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
is >> A.first >> A.second;
return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
os << A.first << ' ' << A.second;
return os;
}
// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
for (size_t i = 0; i < A.size(); i++) {
is >> A[i];
}
return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
for (size_t i = 0; i < A.size(); i++) {
os << A[i];
if (i != A.size() - 1) os << endl;
}
return os;
}
// tuple
template <typename T, size_t N>
struct TuplePrint {
static ostream &print(ostream &os, const T &t) {
TuplePrint<T, N - 1>::print(os, t);
os << ' ' << get<N - 1>(t);
return os;
}
};
template <typename T>
struct TuplePrint<T, 1> {
static ostream &print(ostream &os, const T &t) {
os << get<0>(t);
return os;
}
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
return os;
}
// io functions
void FLUSH() {
cout << flush;
}
void print() {
cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
cout << head;
if (sizeof...(Tail)) cout << spa;
print(std::forward<Tail>(tail)...);
}
template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
int n = A.size();
for (int i = 0; i < n; i++) {
cout << A[i];
if (i != n - 1) cout << sep;
}
cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
cout << A << end;
}
template <typename T>
void prispa(T A) {
priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
if (f)
print(A);
else
print(B);
return f;
}
template <class... T>
void inp(T &...a) {
(cin >> ... >> a);
}
} // namespace io
using namespace io;
// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
vector<vector<int>> edges(n, vector<int>());
for (int i = 0; i < m; i++) {
INT(u, v);
u -= indexed;
v -= indexed;
edges[u].push_back(v);
if (!direct) edges[v].push_back(u);
}
return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
return read_edges(n, n - 1, false, indexed);
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
for (int i = 0; i < m; i++) {
INT(u, v);
T w;
inp(w);
u -= indexed;
v -= indexed;
edges[u].push_back({v, w});
if (!direct) edges[v].push_back({u, w});
}
return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
return read_wedges<T>(n, n - 1, false, indexed);
}
// yes / no
namespace yesno {
// yes
inline bool yes(bool f = true) {
cout << (f ? "yes" : "no") << endl;
return f;
}
inline bool Yes(bool f = true) {
cout << (f ? "Yes" : "No") << endl;
return f;
}
inline bool YES(bool f = true) {
cout << (f ? "YES" : "NO") << endl;
return f;
}
// no
inline bool no(bool f = true) {
cout << (!f ? "yes" : "no") << endl;
return f;
}
inline bool No(bool f = true) {
cout << (!f ? "Yes" : "No") << endl;
return f;
}
inline bool NO(bool f = true) {
cout << (!f ? "YES" : "NO") << endl;
return f;
}
// possible
inline bool possible(bool f = true) {
cout << (f ? "possible" : "impossible") << endl;
return f;
}
inline bool Possible(bool f = true) {
cout << (f ? "Possible" : "Impossible") << endl;
return f;
}
inline bool POSSIBLE(bool f = true) {
cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
return f;
}
// impossible
inline bool impossible(bool f = true) {
cout << (!f ? "possible" : "impossible") << endl;
return f;
}
inline bool Impossible(bool f = true) {
cout << (!f ? "Possible" : "Impossible") << endl;
return f;
}
inline bool IMPOSSIBLE(bool f = true) {
cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
return f;
}
// Alice Bob
inline bool Alice(bool f = true) {
cout << (f ? "Alice" : "Bob") << endl;
return f;
}
inline bool Bob(bool f = true) {
cout << (f ? "Bob" : "Alice") << endl;
return f;
}
// Takahashi Aoki
inline bool Takahashi(bool f = true) {
cout << (f ? "Takahashi" : "Aoki") << endl;
return f;
}
inline bool Aoki(bool f = true) {
cout << (f ? "Aoki" : "Takahashi") << endl;
return f;
}
} // namespace yesno
using namespace yesno;
} // namespace templates
using namespace templates;
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
size = 1;
log = 0;
while (size < _n) {
log++;
size <<= 1;
}
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) update(i);
}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
S prod(int l, int r) {
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S get(int x) {
return prod(x, x + 1);
}
S all_prod() {
return d[1];
}
void apply(int l, int r, F f) {
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) {
d[k] = op(d[2 * k], d[2 * k + 1]);
}
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
const ll inf = 1LL << 60;
struct S {
ll idx;
ll x;
};
S op(S l, S r) {
return l.x > r.x ? l : r;
}
S e() {
return S{-1, -inf};
}
using F = ll;
S mapping(F f, S x) {
return S{x.idx, x.x + f};
}
F composition(F f, F g) {
return f + g;
}
F id() {
return 0;
}
void solve() {
LL(n, m);
vec(ll, A, n + 1);
A[0] = 0;
fori(i, 1, n + 1) inp(A[i]);
A.push_back(m);
VEC(ll, B, n);
sort(all(B));
fori(i, 1, n) B[i] += B[i - 1];
while (B.back() > m) B.pop_back();
vec(S, ini, 2 * n);
fori(i, 2 * n) ini[i] = {i, 0};
lazy_segtree<S, op, e, F, mapping, composition, id> seg(ini);
stack<int> st;
int ap = n;
bool prog = false;
ll bb = -1;
ll ans = 0;
vec(ll, add_, 2 * n);
while (!B.empty()) {
ll b = B.back();
B.pop_back();
while (b <= A[ap]) {
if (prog) {
seg.apply(ap, 2 * n, bb - A[ap]);
st.push(ap);
add_[ap] = bb - A[ap];
} else {
seg.apply(ap, ap + 1, A[ap + 1] - A[ap]);
}
ap--;
prog = false;
}
if (prog) {
auto res = seg.prod(ap, 2 * n);
ans += bb - b;
ans += res.x;
while (!st.empty() and st.top() < res.idx) {
int idx = st.top();
st.pop();
seg.apply(idx, 2 * n, -add_[idx]);
}
seg.apply(res.idx, res.idx + 1, -inf);
bb = b;
continue;
}
auto res = seg.prod(ap, 2 * n);
ll ma1 = res.x;
ll ma2 = A[ap + 1] - b;
if (ma1 >= ma2) {
ans += ma1;
while (!st.empty() and st.top() < res.idx) {
int idx = st.top();
st.pop();
seg.apply(idx, 2 * n, -add_[idx]);
}
seg.apply(res.idx, res.idx + 1, -inf);
} else {
prog = true;
bb = b;
ans += ma2;
}
}
print(ans);
}
int main() {
#ifndef INTERACTIVE
cin.tie(0)->sync_with_stdio(0);
#endif
// cout << fixed << setprecision(12);
int t;
t = 1;
cin >> t;
while (t--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
3 3 10 1 5 9 1 2 3 3 10 1 5 9 1 1 4 3 10 1 5 9 1 5 10
output:
9 9 7
result:
ok 3 number(s): "9 9 7"
Test #2:
score: 0
Accepted
time: 28ms
memory: 3588kb
input:
10000 9 879847766 125098132 150509852 181700303 196375322 519766842 560891576 609151480 721527163 805167083 99031467 66330518 6283986 21388462 41109537 83628243 116141243 144052767 192448599 8 30 5 12 16 19 20 23 25 27 3 1 1 4 2 8 2 3 8 30 4 10 13 16 17 20 23 27 6 3 1 2 3 4 7 2 7 586479012 37693706 ...
output:
858888761 28 27 548785306 28 875933380 27 803763192 942603170 720683076 536166430 759475944 28 27 28 886112586 27 28 28 727698126 28 27 29 28 28 28 28 27 28 819730903 755946410 28 26 28 792662140 891539003 583799124 817190966 934413263 28 28 865467960 27 27 29 488557236 27 26 618111955 28 27 8328741...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 28ms
memory: 3668kb
input:
10000 8 921979410 2012452 24917627 294894613 360777223 466409663 571239725 717231773 737720960 44502046 158432459 29280108 46756101 343060886 113805663 122292234 18336789 9 996365984 93547621 418854579 432723524 452103231 472239725 534297866 551979311 643474068 796448288 94769801 184799140 40559247 ...
output:
897061783 958809789 518874667 508026272 25 817915823 563445073 755045438 917466401 26 27 963697076 28 857532778 28 28 28 599907462 733717366 861642961 553806595 802417186 26 29 29 29 26 27 908132071 816055107 862993074 29 28 27 28 882732250 585539614 900924232 28 556635369 29 890134472 29 636599530 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 24ms
memory: 3612kb
input:
10000 10 693426682 39824378 170753052 172063351 204664113 232271632 245840174 254784959 390184491 453231487 570861818 59595344 22173087 116391450 143121946 23632190 35151525 70352626 30324904 25656706 163522735 8 745209526 121015828 125758181 231986462 461404045 468707947 717366997 738929033 7446472...
output:
655017612 738487472 27 27 626514952 500700122 849903776 29 28 921304686 28 28 28 511049979 28 964808180 611201804 970483767 27 860011940 29 508674850 932159377 948125850 876572563 27 27 575252625 663694866 28 28 27 29 964824235 29 675855993 706402286 754992051 871698228 662676082 27 27 709260574 28 ...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 24ms
memory: 3664kb
input:
10000 9 842080350 126196899 281629390 459021362 589053377 623175793 685983677 686703503 729586222 758579378 139044583 175581708 4917601 53914562 1222336 149353315 84085936 136084484 1513682 10 722336436 66051155 127735998 212633619 309660895 320820247 433981470 582010812 605111593 662898478 67592938...
output:
840138188 695635705 27 488244927 611314272 28 29 776832666 523082033 510786580 29 665355993 834007553 26 28 28 27 596775460 27 601211316 508521258 27 29 618048411 550827368 28 685403346 28 548465042 28 717225955 27 28 882022106 844126870 677316532 649858373 25 28 27 559237354 27 29 497165741 28 5888...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 24ms
memory: 3604kb
input:
10000 8 708514163 23962271 40872775 157099307 187103309 187292974 402257538 501178818 704015400 25220820 70022938 15019601 105088431 93501133 257255953 42050187 77267678 7 30 3 7 14 15 18 25 28 2 2 4 2 5 4 8 10 30 1 3 6 10 14 16 18 21 23 29 1 2 1 1 1 4 3 1 9 2 8 30 6 11 15 19 20 21 26 27 1 1 2 5 12 ...
output:
684362227 27 29 27 28 793316719 779926027 705604988 27 27 29 27 762714343 590862983 651453477 27 29 906481542 609791490 655735160 825013581 27 589806786 769457681 559647071 676833126 28 28 565082202 29 29 29 605930903 736724745 496276423 735975647 27 752861191 498615546 696968479 872153866 847512710...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 25ms
memory: 3636kb
input:
10000 9 30 10 13 17 20 24 26 27 28 29 2 2 2 7 1 2 1 7 1 7 831527343 75686598 280691289 496275248 534534697 652168969 665687389 764253502 41653637 35883907 77174475 169783531 134532994 338354 215483430 8 718484116 100189900 124378121 342235912 403546854 508604060 531760359 621198327 671653286 1603436...
output:
28 817670569 694754999 26 27 812629714 27 553368309 749769223 28 27 869423605 927591951 28 868501917 27 554113115 27 757872877 834811859 28 27 28 29 552439238 735169432 876903178 581459092 28 27 657892555 26 886754984 28 686160103 789538336 981411102 510312850 890648943 770480532 583276901 718986202...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 28ms
memory: 3644kb
input:
10000 10 30 3 4 6 14 17 18 20 22 25 29 2 6 3 3 5 1 3 1 2 2 10 30 6 11 15 16 19 20 23 26 28 29 1 3 2 4 1 4 2 4 2 5 7 600683054 113738178 144331374 193930552 194822106 386416391 476890041 530562637 128835461 23989891 53437985 88589084 2092213 37690603 190105270 8 853858494 17017766 188244392 228267168...
output:
28 28 597699287 797386235 727159057 565049429 828474455 27 895177696 28 594056778 912193740 27 620191871 852100623 29 28 27 943358883 580553291 26 29 29 642061746 28 874798456 27 541562041 28 29 642682965 27 28 824610759 28 486459828 704550861 483902395 29 28 27 28 618648751 633419081 533827057 28 2...
result:
ok 10000 numbers
Test #9:
score: 0
Accepted
time: 28ms
memory: 3608kb
input:
10000 10 794490958 33950165 102613172 233931653 294328727 365866988 394195990 502295599 533500764 697722342 789065736 117636901 56842505 67344689 12693883 43898025 33184559 25296165 165237670 98913433 85684653 7 583412616 79630060 103778160 178797644 347021280 412084871 412242198 437485086 22767799 ...
output:
760540793 554564585 27 28 956701395 25 29 28 28 27 28 28 28 616705831 26 28 28 28 28 27 27 27 470127478 28 562109534 638390996 937834685 702323118 665789596 734137704 26 28 826636157 645678237 641375059 791320618 769654094 28 27 868850069 836416112 29 29 28 825545237 831096007 29 28 579941952 28 29 ...
result:
ok 10000 numbers
Test #10:
score: 0
Accepted
time: 28ms
memory: 3836kb
input:
10000 7 620163263 2210088 111033028 213072508 221754874 270340156 465271372 605401151 6589256 133531932 80578109 1717576 194259279 19940297 73135525 8 821458748 94147403 103911199 119213944 148910116 274334138 396035434 415716320 720330739 17483998 40595682 113502043 152348211 87133614 140810847 126...
output:
617953175 759227323 28 577328355 863285321 667218327 29 28 27 28 815536760 559280576 503382454 27 854334502 533028547 967848554 28 767236520 527447546 27 28 625532436 557267576 964127503 27 941231576 648972067 627806338 27 27 685426661 28 27 500624304 27 896818489 29 29 762801184 27 28 27 28 28 7797...
result:
ok 10000 numbers
Test #11:
score: 0
Accepted
time: 24ms
memory: 3904kb
input:
10000 8 748462261 126938743 298205026 460858560 493696867 561517982 598369982 611594963 660762051 9836010 43420294 113911448 87081999 64171127 65191414 117828249 86952635 9 818975929 111152475 125419210 135487970 248358986 365050068 500993620 620295174 693052429 740583941 4529198 15575283 36039923 1...
output:
725401270 790111236 28 742737637 803407267 947164183 576552794 29 27 28 29 28 28 874730861 27 855768639 26 28 911087029 26 28 27 583592147 28 813229697 26 614462355 28 514365649 28 621277915 27 472160914 860353209 559573286 28 27 728087897 26 726726326 28 29 855714743 880622108 27 28 924203964 27 85...
result:
ok 10000 numbers
Test #12:
score: 0
Accepted
time: 24ms
memory: 3640kb
input:
10000 8 796414787 31461520 50761715 90495707 251124998 341850881 720825960 773620389 780205466 54722380 216907544 23636692 98146858 23139876 206884562 69929854 45979367 8 870995852 157940387 214396482 255563234 292144526 336132163 634226211 655076826 795592633 219513340 91244154 123598065 6795235 13...
output:
762693039 806768710 736355372 26 28 28 729100973 862887449 570384939 28 594631648 676565090 28 913095700 562500308 673390494 28 28 655289472 27 28 28 28 29 888685546 690676876 835447840 632836562 666794814 28 908883242 864921023 643425480 652704139 29 893801977 848367692 681211139 760058749 61436934...
result:
ok 10000 numbers
Test #13:
score: 0
Accepted
time: 83ms
memory: 19356kb
input:
1 93849 788867517 27106 35801 44166 45367 71580 75909 79832 80217 88191 125196 128361 161338 162562 166454 169706 187030 193620 198170 213307 218172 219965 224851 227874 234787 249446 254210 260203 261675 266494 275046 281192 287637 294087 302671 329113 334903 352098 375155 393228 400443 406748 4227...
output:
788867514
result:
ok 1 number(s): "788867514"
Test #14:
score: 0
Accepted
time: 94ms
memory: 19300kb
input:
1 96398 922474561 1901 2788 13435 21334 21715 32835 37906 50378 60713 63368 72102 79312 89180 93296 98588 109931 111175 112094 128772 131828 133586 135397 138806 139916 144874 153088 182296 199243 203880 203963 204287 206706 206814 212347 219070 224608 228339 232690 244468 250015 252724 266841 27237...
output:
922474558
result:
ok 1 number(s): "922474558"
Test #15:
score: 0
Accepted
time: 84ms
memory: 19076kb
input:
1 90089 742727663 1217 6823 13314 18050 24731 28352 42997 49561 55040 61758 70988 83872 92015 94583 130355 130462 134637 140652 144576 145902 148292 155581 155868 166731 177106 194744 209712 231894 232938 236413 240680 241753 243178 243375 250977 269081 271541 276802 298463 305980 312949 318614 3306...
output:
742727661
result:
ok 1 number(s): "742727661"
Test #16:
score: 0
Accepted
time: 89ms
memory: 19072kb
input:
1 91457 958286812 4576 10232 12013 36690 43036 75552 78919 83507 87580 95811 98869 103602 117510 124332 134780 145656 146869 149969 154497 155954 166010 181781 197212 200887 221994 232743 244628 247812 269153 275367 277923 279230 306333 311159 311796 313583 315548 326592 339643 353158 355861 410756 ...
output:
958286810
result:
ok 1 number(s): "958286810"
Test #17:
score: 0
Accepted
time: 87ms
memory: 19376kb
input:
1 96636 946300936 1934 10123 19340 33428 51855 58257 62986 64601 69149 84284 86204 100279 108754 109464 116710 125731 142727 155341 195026 227414 235495 248717 251184 296436 297163 300170 301264 312881 317358 332543 333984 372889 376568 391504 405260 410727 415870 436541 442341 446510 449309 460153 ...
output:
946300933
result:
ok 1 number(s): "946300933"
Test #18:
score: 0
Accepted
time: 87ms
memory: 19284kb
input:
1 94463 828132301 542 7003 17038 17374 25312 35177 36656 45415 56758 61075 63587 69933 80702 85732 88898 90611 92986 102266 119807 130948 144192 144289 168919 177198 180392 184131 198442 198628 208736 209804 223497 224487 233230 250463 252862 253768 276441 281549 292476 304007 304196 307425 311458 3...
output:
828132298
result:
ok 1 number(s): "828132298"
Test #19:
score: 0
Accepted
time: 89ms
memory: 19832kb
input:
1 99386 856358032 9342 9789 15768 18347 29826 32298 37146 38716 40663 47080 58496 77227 80563 86981 87770 88422 93717 108195 109329 123588 131010 146152 148141 151411 154282 167351 176879 200229 200934 204370 207654 211060 213202 231489 235581 243411 245746 247478 255086 256528 272684 294411 307780 ...
output:
856358030
result:
ok 1 number(s): "856358030"
Test #20:
score: 0
Accepted
time: 91ms
memory: 19568kb
input:
1 99942 623445854 982 3331 10251 12748 30485 32159 49296 50512 55319 55687 82035 82574 94924 96836 99176 102414 103630 110474 111946 118759 120206 123390 129224 129298 136940 158783 164951 172817 174836 178804 184460 191101 191325 197909 217538 220281 231269 237586 239146 241407 250407 251311 259801...
output:
623445852
result:
ok 1 number(s): "623445852"
Test #21:
score: 0
Accepted
time: 91ms
memory: 19368kb
input:
1 95819 844006123 11453 12062 15525 20176 21653 41258 47316 60272 66576 93784 112286 119375 124809 132817 133053 135731 153151 154062 157182 157782 164364 169065 172029 173121 183564 192849 212900 213437 216589 224462 226749 235646 263949 272370 274975 274998 276231 281002 291211 311728 313567 31970...
output:
844006121
result:
ok 1 number(s): "844006121"
Test #22:
score: 0
Accepted
time: 84ms
memory: 19324kb
input:
1 93880 546964419 2938 9927 12958 13151 15391 15718 15812 18174 19487 23743 25343 30417 33954 36426 37278 43055 47143 51426 51900 53292 57316 72434 73105 74128 84406 85453 87082 90728 91445 93245 101854 105770 112370 119339 127949 135934 136058 138343 142476 146026 151741 155635 157622 159642 160008...
output:
546964417
result:
ok 1 number(s): "546964417"
Test #23:
score: 0
Accepted
time: 92ms
memory: 19828kb
input:
1 98812 961793551 3616 12679 15790 22833 33885 41959 70817 78699 85656 112851 128769 130690 136491 146925 154819 186242 189811 190091 195553 208681 231515 240489 263384 290850 292743 294292 305578 308416 309301 310271 314676 332338 337413 341230 346650 349548 352528 353891 364497 365545 380945 38191...
output:
961793548
result:
ok 1 number(s): "961793548"
Test #24:
score: 0
Accepted
time: 51ms
memory: 19684kb
input:
1 100000 1000000000 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000 100000 105000 110000 115000 120000 125000 130000 135000 140000 145000 150000 155000 160000 165000 170000 175000 180000 185000 190000 195000 200000 205000 210000 215000...
output:
749990000
result:
ok 1 number(s): "749990000"
Test #25:
score: 0
Accepted
time: 23ms
memory: 3608kb
input:
10000 8 720924919 9465427 67948940 69494408 141211447 229699002 635895220 662717937 682981723 412345110 48719110 720924919 720924919 720924919 720924919 720924919 720924919 7 30 1 7 8 19 21 23 24 2 3 2 5 8 10 30 8 30 1 5 7 10 11 15 24 30 2 3 30 30 30 30 30 30 9 30 2 6 7 14 16 21 23 24 28 3 5 5 2 1 1...
output:
444139414 26 15 28 25 26 23 409111591 105252716 26 263082702 266803498 17 11 10 9 97193415 718104325 216551531 663010924 679526925 1 13 26 759768185 25 446871193 532540252 217123161 19 22 859870981 703430943 464548891 21 662490758 633056709 26 25 12 27 843265256 618172231 870394919 442218334 21 24 6...
result:
ok 10000 numbers
Test #26:
score: 0
Accepted
time: 23ms
memory: 3864kb
input:
10000 10 852439504 8030778 94697149 126616560 196288942 213547889 232174173 320262103 396019314 737101891 766336993 57064676 312356378 19228807 268670689 31945461 38465787 852439504 852439504 852439504 852439504 7 30 1 2 5 9 11 14 27 5 3 3 14 30 30 30 8 620393221 22413042 141613203 143478860 1835261...
output:
716814847 23 409242319 454281560 21 235022073 506308552 309975288 797975338 548662792 415575198 28 794637505 807472244 19 25 869782051 25 11 622062939 501430743 27 448380057 639999485 463106414 10 606924724 782981521 26 477961466 26 952695625 333091278 22 859544924 702599301 19 468195707 329389391 2...
result:
ok 10000 numbers
Test #27:
score: 0
Accepted
time: 21ms
memory: 3640kb
input:
10000 8 30 4 8 10 17 20 21 24 30 18 3 4 4 30 30 30 30 7 637172131 21550835 66529272 141827983 431002383 525759222 541617986 554428893 3957828 315739155 10197023 72104531 48919779 364607 182334718 10 30 1 3 7 8 11 16 21 26 29 30 25 30 30 30 30 30 30 30 30 30 9 30 3 5 16 17 21 23 25 26 27 1 8 13 2 30 ...
output:
17 608137853 3 20 706750621 311748892 28 19 22 446192291 21 8 18 160811280 117553682 276153368 7 22 8 679025323 18 686399606 761478576 559476806 28 6 2 21 726933409 2 25 11 26 706427322 736150007 17 19 531680320 867086855 363402927 532593615 26 40095414 4 28 17 550467192 13 592649091 19 27 19 26 188...
result:
ok 10000 numbers
Test #28:
score: 0
Accepted
time: 23ms
memory: 3872kb
input:
10000 10 525555127 22660876 67007260 106301240 178512608 197830931 243266860 243313266 258872639 465022582 471341779 12533746 49649344 22255856 82743749 19327238 37909573 65108888 62431762 60842729 104906435 10 631177236 82333932 130336765 207925786 247765703 358205020 456517029 502067905 577796920 ...
output:
496770236 396185680 523306582 853807818 25 620565760 22 26 493128763 259558988 9 811267727 7 297293779 973078431 387555027 675338739 27 23 763330069 23 28 259383269 76646841 551176605 9 20 318003762 24 24 349552267 701775190 28 504364890 27 620685649 567776438 180802390 17 19 2 522565982 483453964 4...
result:
ok 10000 numbers
Test #29:
score: 0
Accepted
time: 19ms
memory: 3676kb
input:
10000 8 631495946 10320116 88036613 141985663 217227311 231465454 388813844 530605984 575446189 19506558 54009097 65876927 70516136 79504988 57965180 129176590 134330206 7 645928837 6688071 23257469 298415461 344781389 387454270 459619210 639384034 51182665 200995838 4031816 125874016 645928837 6459...
output:
597751245 573453684 62981416 333185472 23 17 275460832 135082278 575644503 24 18 773295799 22 835782021 9 209693254 18 84634839 27 9 484441051 20 25 90312880 83025500 29 5 921903776 26 399150435 566858540 10 533260638 537191950 13 22 193695439 21 14 385584554 400231309 20 606396301 643582432 27 8454...
result:
ok 10000 numbers
Test #30:
score: 0
Accepted
time: 20ms
memory: 3604kb
input:
10000 10 900025869 10703771 102406696 262042800 273183576 288245684 401909775 425645891 439651291 480612404 689722431 419653197 53597605 35356251 900025869 900025869 900025869 900025869 900025869 900025869 900025869 9 591339581 142556598 144783196 153368171 210823932 231122305 302908777 358415227 52...
output:
579049569 549871639 20 4 742139204 918878716 17 26 870238745 237698632 5 27 5 21 102900306 492364068 20 314211208 888898877 14 457194530 29 162642388 657794379 23 715119216 809554696 100384288 14 27 473695047 17 169308803 17 636420013 886709295 9 581565050 24 607114451 550243654 788169824 10 27 28 4...
result:
ok 10000 numbers
Test #31:
score: 0
Accepted
time: 20ms
memory: 3536kb
input:
10000 7 30 5 6 8 10 17 23 24 6 5 12 4 30 30 30 9 30 1 2 5 8 10 13 15 23 27 1 27 30 30 30 30 30 30 30 10 30 4 5 7 12 16 18 21 22 25 30 1 2 2 1 2 5 11 2 2 2 9 30 5 7 8 16 17 19 21 22 30 22 1 7 30 30 30 30 30 30 7 30 7 8 16 17 18 19 23 2 2 11 7 2 3 30 10 775020935 28412091 49996866 299225828 420894665 ...
output:
19 10 28 16 25 686128914 10 20 603325531 722751652 10 668061045 29 20 20 15 388296521 878473954 338868599 27 259289369 26 632044420 642815532 8 26 445507395 22 9 474288778 25 637551859 10 242467880 688198610 279617576 25 285729037 602795167 28 611782175 520868246 5 162344523 881135015 18 17 42635349...
result:
ok 10000 numbers
Test #32:
score: 0
Accepted
time: 23ms
memory: 3640kb
input:
10000 9 30 3 5 12 14 20 23 24 26 30 3 3 5 6 3 2 4 1 1 7 30 2 8 9 10 11 12 19 1 3 1 9 1 1 13 8 962324940 158538075 316947422 412399052 508116684 669131782 870874179 880214903 910448953 277848957 21966537 76384640 13909969 2752338 419343157 103786222 962324940 10 747409716 41638238 86026694 92725023 9...
output:
28 27 914454961 736918262 264253076 27 6 26 24 4 5 20 747065933 96517011 19 584068932 18 28 347412547 206186516 25 684464397 3 441689152 17 28 431239841 17 11 8 4 759993546 117835609 75776199 15 576033457 23 18 59213463 8 27 8 651968569 21 25 748089764 470090565 280271977 560422149 631444457 2542545...
result:
ok 10000 numbers
Test #33:
score: 0
Accepted
time: 23ms
memory: 3900kb
input:
10000 8 30 2 3 5 11 16 17 21 29 5 13 11 30 30 30 30 30 9 518824150 139129154 148935761 307233207 313641375 324465840 359433951 408463762 481139814 513013298 57764983 219458835 64836763 15644143 42029651 7815225 518824150 518824150 518824150 9 660753785 15867881 50983151 57052895 263529865 282012905 ...
output:
15 478158833 475681772 27 182771914 315387260 21 28 488283847 922078891 27 718288243 1 25 501461541 582519738 12 12 674192106 388614553 25 662861148 680266039 10 377004630 21 14 241692770 25 20 374970632 8 435226985 28 186034041 469186248 531441787 798142857 16 23 27 21 22 606631344 27 621707320 596...
result:
ok 10000 numbers
Test #34:
score: 0
Accepted
time: 20ms
memory: 3828kb
input:
10000 10 30 2 3 7 8 9 15 16 20 27 30 13 30 30 30 30 30 30 30 30 30 7 933728118 189486626 255278235 286567027 669812847 721577939 779122330 841789602 80888658 255234697 67241224 117894521 14359838 107943417 116784692 8 30 1 3 15 20 24 25 29 30 5 5 3 2 9 1 1 4 8 915666642 177619838 217661287 300982552...
output:
7 888079488 29 673153095 574382933 3 859169762 410513007 27 58773552 450402126 21 11 649244396 13 616887633 351986861 19 705661660 721718578 901443528 26 758240918 25 5 9 372116223 299135648 834262541 19 399222385 471631110 28 28 504344401 27 26 23 17 25 18 667336702 16 7 26 18 5 25 192321604 26 26 ...
result:
ok 10000 numbers
Test #35:
score: 0
Accepted
time: 23ms
memory: 3668kb
input:
10000 10 30 2 9 11 17 19 20 23 25 27 30 22 1 2 30 30 30 30 30 30 30 7 30 1 11 13 17 19 20 21 10 9 4 30 30 30 30 10 945394895 64236786 166246588 207801481 311231593 325288919 452715036 545260108 651389426 658448727 896563952 136738788 487076849 945394895 945394895 945394895 945394895 945394895 945394...
output:
16 18 365541342 448297527 24 805860707 536834580 143408097 334541880 495494276 663427841 26 20 19 22 11 242052294 295601986 11 21 23 274537793 516565192 277435597 713796207 398092064 28 575166166 428716649 393853730 223779893 26 25 253131922 439176964 263979795 22 247829963 896654010 17 153075857 28...
result:
ok 10000 numbers
Test #36:
score: 0
Accepted
time: 51ms
memory: 19508kb
input:
1 94517 842160426 7997 17525 17885 22398 28674 34647 47099 52537 53426 59089 60469 63314 65463 66566 70312 70551 74164 74477 81182 85902 96146 102899 107890 110732 121756 121791 132223 152172 161199 190279 202477 211477 231150 235521 253503 273346 276007 276840 279878 293753 295273 307261 313404 322...
output:
594721376
result:
ok 1 number(s): "594721376"
Test #37:
score: 0
Accepted
time: 33ms
memory: 19760kb
input:
1 98928 742396981 305 21968 23497 33360 34124 43973 44949 46498 53295 56056 58084 82663 94624 103101 117662 118858 122310 128363 133072 160407 161528 166619 213940 222129 224653 227698 236035 238352 239692 242480 289534 293344 309523 311945 331188 333508 338923 343147 347729 368426 388781 391367 393...
output:
125334053
result:
ok 1 number(s): "125334053"
Test #38:
score: 0
Accepted
time: 53ms
memory: 19360kb
input:
1 94266 603438255 19820 22915 24175 25317 26083 35208 37253 39147 46150 54696 59700 83245 86483 97949 101899 107249 107408 113851 127023 131959 136671 140834 152637 155361 157134 159235 171918 172628 173752 188413 193288 200113 218247 234705 239121 246762 249938 251356 258408 271214 271356 279498 30...
output:
383944560
result:
ok 1 number(s): "383944560"
Test #39:
score: 0
Accepted
time: 42ms
memory: 19708kb
input:
1 98699 629317659 13027 14114 25666 32825 35316 37087 42547 52617 58556 58933 71840 73879 103972 105129 116521 121288 121416 134678 140920 142178 155129 163109 164029 174576 176210 196079 196151 198545 205864 210262 214337 217345 219245 219250 229157 247350 257036 261420 265641 267349 269077 272799 ...
output:
344132848
result:
ok 1 number(s): "344132848"
Test #40:
score: 0
Accepted
time: 39ms
memory: 19392kb
input:
1 96636 946300936 1934 10123 19340 33428 51855 58257 62986 64601 69149 84284 86204 100279 108754 109464 116710 125731 142727 155341 195026 227414 235495 248717 251184 296436 297163 300170 301264 312881 317358 332543 333984 372889 376568 391504 405260 410727 415870 436541 442341 446510 449309 460153 ...
output:
311918114
result:
ok 1 number(s): "311918114"
Test #41:
score: 0
Accepted
time: 75ms
memory: 19748kb
input:
1 97696 579464370 8030 15511 21486 24001 30107 34762 53443 59898 60387 62722 67757 70631 76477 81575 83763 88614 92168 119884 132234 144106 153327 154838 155621 179623 186389 192875 204987 210201 211904 216555 216992 219936 220883 230739 231644 240896 241845 246104 254952 255189 261181 262528 266881...
output:
549602254
result:
ok 1 number(s): "549602254"
Test #42:
score: 0
Accepted
time: 64ms
memory: 19256kb
input:
1 92686 737634633 6319 15460 30331 30895 36248 49722 54264 55401 55968 59110 63434 74760 78538 85258 86904 87541 121413 122456 132640 135898 146288 150010 160173 165175 170005 170584 176752 186758 191745 193505 203042 210889 213740 221030 230311 241208 243684 253381 259417 259801 264884 265572 27176...
output:
648866979
result:
ok 1 number(s): "648866979"
Test #43:
score: 0
Accepted
time: 56ms
memory: 19384kb
input:
1 96436 664778097 4942 7854 19110 29066 39055 50424 51557 55772 58209 66227 66539 74733 90732 91669 102226 106423 110443 115736 121112 126495 127437 129247 131094 132729 134073 154746 162084 163873 165019 175514 176870 187763 190946 194978 231950 237308 239955 254888 254981 260086 261484 263998 2853...
output:
567392110
result:
ok 1 number(s): "567392110"
Test #44:
score: 0
Accepted
time: 38ms
memory: 19432kb
input:
1 95873 851845143 10479 11790 21564 23968 29158 44282 56238 57840 67404 68642 91524 109788 111853 125465 129609 132464 133162 138089 150298 156419 170545 174250 176359 192639 192771 201890 206804 216030 218450 224653 229115 249016 251743 253291 254991 255654 267633 279410 303286 303436 304222 304887...
output:
92755585
result:
ok 1 number(s): "92755585"
Test #45:
score: 0
Accepted
time: 49ms
memory: 19324kb
input:
1 93869 768451236 3446 11644 11945 18193 23768 24581 36355 38576 40047 40235 61127 62532 64175 65440 74656 78401 79941 86183 101593 112196 120209 126021 136276 147914 148420 148538 177028 187025 193349 194054 197291 205779 208653 213278 222597 234582 241977 245720 250684 274332 282942 285740 301003 ...
output:
473709177
result:
ok 1 number(s): "473709177"
Test #46:
score: 0
Accepted
time: 77ms
memory: 19104kb
input:
1 91528 500984411 21352 24754 26888 31923 39233 50086 79257 85736 99255 110065 134760 140931 141849 142314 143998 147202 149899 150989 155622 156494 166121 167313 177112 185066 190595 191102 191472 198655 202762 203252 204886 212948 237644 250529 260595 263018 268152 269306 269542 285671 300026 3001...
output:
497448795
result:
ok 1 number(s): "497448795"
Test #47:
score: 0
Accepted
time: 13ms
memory: 19704kb
input:
1 100000 1000000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 9...
output:
0
result:
ok 1 number(s): "0"
Extra Test:
score: 0
Extra Test Passed