QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235631 | #665. Boxes and Balls | ckiseki | AC ✓ | 27ms | 7256kb | C++20 | 4.4kb | 2023-11-02 23:03:04 | 2023-11-02 23:03:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef local
#include <experimental/iterator>
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
template <typename F, typename C> class MCMF {
static constexpr F INF_F = numeric_limits<F>::max() / 3;
static constexpr C INF_C = numeric_limits<C>::max() / 3;
struct E {
int to, r;
F f; C c;
E() {}
E(int a, int b, F x, C y)
: to(a), r(b), f(x), c(y) {}
};
int n;
array<vector<E>, 40000> g;
vector<pair<int, int>> f;
vector<bool> inq;
vector<F> up; vector<C> d, h;
optional<pair<F, C>> step(int S, int T) {
safe;
debug(S, T);
priority_queue<pair<C, int>> q;
q.emplace(d[S] = 0, S), up[S] = INF_F;
while (not q.empty()) {
auto [l, u] = q.top(); q.pop();
debug(u, l, -d[u]);
assert(-l >= d[u]);
assert(up[u] != 0);
if (l != -d[u]) continue;
for (int i = 0; i < int(g[u].size()); ++i) {
auto e = g[u][i]; int v = e.to;
debug(u, v, e.c + h[u] - h[v]);
if (e.f > 0)
assert(e.c + h[u] - h[v] >= 0);
auto nd = d[u] + e.c + h[u] - h[v];
if (e.f <= 0 or d[v] <= nd) continue;
f[v] = {u, i}; up[v] = min(up[u], e.f);
q.emplace(-(d[v] = nd), v);
}
}
if (d[T] == INF_C) return nullopt;
for (size_t i = 0; i < d.size(); ++i)
h[i] += d[i];
for (int i = T; i != S; i = f[i].first) {
auto &eg = g[f[i].first][f[i].second];
eg.f -= up[T]; g[eg.to][eg.r].f += up[T];
}
return pair{up[T], h[T]};
}
void precalc(int a) {
d[a] = 0;
for (int _ = 0; _ <= n; _++) {
bool flag = false;
for (int u = 0; u < n; u++)
if (d[u] != INF_C)
for (int i = 0; i < int(g[u].size()); ++i) {
auto e = g[u][i]; int v = e.to;
auto nd = d[u] + e.c;
if (e.f <= 0 or d[v] <= nd) continue;
d[v] = nd;
flag = true;
}
if (_ == n) assert(!flag);
if (!flag)
break;
}
orange(all(d));
assert(h.size() == d.size());
for (size_t i = 0; i < d.size(); ++i)
h[i] = d[i];
debug(INF_C);
fill(d.begin(), d.end(), INF_C);
}
public:
MCMF(int n_) : n(n_), f(n), inq(n), up(n), d(n, INF_C), h(n) {}
void add_edge(int s, int t, F c, C w) {
g[s].emplace_back(t, int(g[t].size()), c, w);
g[t].emplace_back(s, int(g[s].size()) - 1, 0, -w);
}
pair<F, C> solve(int a, int b) {
precalc(a);
F c = 0; C w = 0;
while (auto r = step(a, b)) {
c += r->first, w += r->first * r->second;
fill(d.begin(), d.end(), INF_C);
}
return {c, w};
}
};
using lld = int64_t;
using ll = lld;
const int N = 10025;
int lst[N], wei[N];
const ll MAXC = 1e9;
const ll INF = 1e18;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int m, n, k;
ll ans = 0;
cin >> m >> n >> k;
int S = 0, T = 2 * k + 1;
MCMF<lld,lld> mcmf(2 * k + 2);
// mcmf.init(2 * k + 2);
for (int i = 1; i <= n; ++i)
cin >> wei[i];
mcmf.add_edge(S, 1, m, 0);
mcmf.add_edge(2 * k, T, m, 0);
for (int i = 1; i <= k; ++i) {
mcmf.add_edge(2 * i - 1, 2 * i, 1, -MAXC);
mcmf.add_edge(2 * i - 1, 2 * i, INF, 0);
if (i < k)
mcmf.add_edge(2 * i, 2 * i + 1, INF, 0);
}
for (int i = 1; i <= k; ++i) {
int x;
cin >> x;
if (lst[x]) mcmf.add_edge(2 * lst[x], 2 * i - 1, 1, -wei[x]);
lst[x] = i;
ans += wei[x];
}
auto [flow, cost] = mcmf.solve(S, T);
cout << ans + k * MAXC + cost << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4400kb
input:
3 3 6 10 20 30 1 2 3 1 2 3
output:
60
result:
ok single line: '60'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
2 3 6 10 20 30 1 2 3 1 2 3
output:
80
result:
ok single line: '80'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4340kb
input:
1 1 1 8916 1
output:
8916
result:
ok single line: '8916'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4680kb
input:
1 1 1000 1319 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1319
result:
ok single line: '1319'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
1 10 1 7222 7541 665 6138 6834 8472 9450 7323 8223 1183 7
output:
9450
result:
ok single line: '9450'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4684kb
input:
1 10 1000 7645 9162 2432 247 2559 3504 5683 3825 5884 5197 6 3 7 4 8 1 10 1 4 3 4 2 4 2 4 8 2 8 5 1 6 2 6 10 10 5 1 10 9 9 7 9 7 4 2 3 6 3 6 7 8 5 4 6 7 5 7 3 5 3 8 10 8 8 3 10 8 5 10 1 10 3 10 2 3 10 2 6 8 5 8 8 2 5 1 6 5 10 3 10 2 4 6 10 4 1 5 5 1 7 9 5 9 2 9 10 9 3 1 3 3 4 3 10 8 5 9 2 10 3 8 5 4...
output:
4099952
result:
ok single line: '4099952'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4352kb
input:
3 1 1 2193 1
output:
2193
result:
ok single line: '2193'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4652kb
input:
3 1 1000 4065 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
4065
result:
ok single line: '4065'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4360kb
input:
3 10 1 1235 3867 1554 3069 6439 3353 7630 6785 2834 9499 10
output:
9499
result:
ok single line: '9499'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4684kb
input:
3 10 1000 5576 7215 3323 7713 5442 6754 2558 9114 4401 1911 3 6 7 4 6 1 1 3 2 2 2 4 9 3 3 6 5 10 5 2 4 9 5 5 1 5 6 7 10 5 6 7 7 7 8 2 2 1 6 10 3 2 4 2 6 1 4 3 1 6 5 9 4 1 8 10 7 4 5 4 8 1 10 8 4 8 7 1 5 5 4 3 8 1 1 1 5 3 4 8 10 7 10 2 4 3 7 3 2 7 8 1 4 4 7 9 1 9 10 3 10 8 7 6 9 3 7 1 7 10 6 5 1 2 9 ...
output:
2462043
result:
ok single line: '2462043'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4424kb
input:
2 5 207 3986 4810 4235 9030 5231 1 5 2 3 4 3 1 4 1 3 5 3 4 4 4 2 1 1 3 3 2 4 1 1 4 1 5 3 2 2 4 5 3 4 4 4 4 1 1 5 3 1 2 1 5 2 2 4 1 3 2 5 2 1 2 3 5 3 3 3 1 2 1 4 2 4 4 3 1 2 3 5 5 2 2 3 3 2 2 2 2 5 2 5 1 5 3 2 1 2 5 2 2 2 2 2 5 5 1 2 5 5 5 4 4 2 5 5 1 2 1 3 4 4 2 1 1 3 4 1 4 5 1 1 3 2 5 2 5 2 1 5 1 3...
output:
472094
result:
ok single line: '472094'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4504kb
input:
3 10 142 9266 518 4888 4135 4691 7518 7861 6633 3574 8521 5 5 1 9 10 7 2 3 4 6 1 1 10 5 9 9 4 8 7 8 5 3 6 4 5 2 6 7 3 10 9 6 1 3 9 2 5 8 5 1 4 3 8 5 1 8 10 10 6 8 7 1 10 7 8 5 6 3 10 4 1 9 3 8 9 3 6 4 8 3 3 10 2 10 2 10 8 3 6 2 5 10 7 3 3 3 1 6 4 10 1 3 8 7 9 1 1 10 7 6 10 9 3 9 9 4 5 3 6 4 2 8 1 3 ...
output:
409815
result:
ok single line: '409815'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4460kb
input:
1 5 301 4045 2565 2318 2100 1010 2 4 5 5 5 5 2 1 3 5 2 2 4 3 5 2 1 3 4 2 5 3 1 1 1 1 2 1 3 2 5 2 3 2 1 1 3 3 1 1 4 5 5 3 3 4 2 1 2 5 3 1 3 1 5 5 2 1 5 1 1 3 3 4 5 5 3 5 2 5 1 4 4 3 1 2 1 5 3 1 5 3 5 1 4 4 1 5 3 5 4 3 2 5 5 3 2 3 1 4 5 2 4 3 4 2 2 3 3 1 5 2 2 4 1 2 3 2 4 4 5 5 5 2 5 5 4 3 4 1 2 3 1 5...
output:
601566
result:
ok single line: '601566'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4508kb
input:
3 4 461 8190 7387 4037 5056 2 3 4 1 4 4 4 3 1 4 4 4 3 2 2 1 4 2 1 2 3 4 1 1 1 4 1 4 2 2 4 3 2 4 1 1 1 3 4 1 3 2 4 3 1 4 3 1 3 1 2 4 3 4 4 4 3 2 2 4 2 4 4 1 4 4 3 4 4 1 2 4 3 3 2 3 2 1 1 1 3 4 1 4 3 3 1 1 4 3 1 3 2 4 1 4 2 4 4 3 3 3 4 2 3 3 3 2 2 4 4 2 1 3 4 3 1 2 3 3 4 3 2 1 2 1 4 2 3 3 1 4 4 2 3 3 ...
output:
406074
result:
ok single line: '406074'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4332kb
input:
3 3 85 459 8759 3043 1 3 2 3 2 3 2 1 2 2 2 2 1 2 2 2 2 3 1 1 3 3 2 1 3 1 1 3 3 1 2 2 2 1 2 1 2 3 2 2 3 3 1 2 1 2 1 1 3 3 2 3 3 2 1 1 1 1 1 2 3 1 3 3 2 2 2 3 1 2 2 3 1 2 2 1 3 1 1 1 2 2 3 2 1
output:
12261
result:
ok single line: '12261'
Test #16:
score: 0
Accepted
time: 1ms
memory: 4580kb
input:
2 6 330 6412 3092 4584 8719 3590 7095 1 2 4 4 5 2 1 1 6 4 4 5 2 6 5 5 6 1 1 1 4 6 2 1 4 1 3 3 2 4 3 6 4 4 5 6 4 3 3 4 5 3 3 4 5 5 5 3 4 2 4 4 5 3 5 2 1 1 4 5 5 6 2 5 4 6 6 2 3 6 2 6 1 1 2 6 1 2 2 6 5 6 5 6 1 3 1 3 4 4 3 2 3 5 6 1 4 3 2 3 3 4 6 1 2 6 4 5 2 3 3 4 5 4 2 3 2 3 3 4 4 1 2 1 5 3 4 6 5 2 2 ...
output:
894825
result:
ok single line: '894825'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4648kb
input:
2 8 928 8867 1733 4402 5256 355 2130 8045 6421 7 2 2 6 6 4 3 8 5 2 1 2 5 1 4 4 8 5 6 3 7 5 2 5 3 6 6 5 5 3 4 3 4 7 6 6 3 7 2 1 6 4 1 4 2 1 6 7 2 8 6 2 2 4 6 8 5 3 1 4 3 2 1 3 2 7 3 2 4 6 7 1 6 2 7 5 5 3 4 6 1 2 5 7 5 6 7 3 8 1 8 6 1 8 5 3 2 4 6 1 3 5 1 1 4 6 1 5 8 6 6 1 8 7 8 5 6 2 1 7 1 3 3 3 4 4 1...
output:
2346574
result:
ok single line: '2346574'
Test #18:
score: 0
Accepted
time: 2ms
memory: 4608kb
input:
3 6 839 1129 3880 9479 1529 1536 4689 2 4 4 2 4 1 5 3 1 2 4 4 2 1 5 1 5 5 2 2 5 2 6 5 2 4 4 2 2 4 1 5 1 5 1 4 5 1 1 2 6 6 5 4 6 4 4 1 2 4 2 5 5 2 4 1 5 5 2 6 6 5 6 6 2 2 2 5 2 4 1 3 1 4 2 3 5 4 6 1 6 6 4 1 4 5 5 6 6 4 6 6 2 4 2 1 2 3 5 2 2 5 4 6 2 4 5 3 6 2 5 6 4 3 1 4 5 5 3 2 1 5 5 4 5 3 2 3 4 3 6 ...
output:
682015
result:
ok single line: '682015'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4408kb
input:
3 10 233 1280 1604 6589 590 7042 28 5408 9905 8797 4796 3 8 2 9 10 10 5 6 2 5 6 2 6 1 2 4 4 1 7 10 8 5 10 5 10 3 10 2 6 2 10 4 1 9 5 5 1 5 9 10 9 2 4 7 4 3 2 4 10 8 2 6 10 10 2 3 9 9 7 10 1 3 9 3 3 9 3 6 2 6 3 9 5 4 6 7 6 4 7 6 5 2 1 5 5 7 3 8 2 9 5 5 5 6 5 3 3 4 1 10 10 1 7 8 5 1 3 10 9 10 5 10 7 2...
output:
417958
result:
ok single line: '417958'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4376kb
input:
1 8 51 4691 116 5044 5379 4979 3426 9807 8814 4 6 8 3 8 7 1 3 2 7 1 8 5 6 7 3 1 8 7 5 3 7 5 7 7 5 2 7 2 8 2 1 4 4 1 4 4 7 8 3 6 1 1 2 3 7 7 8 1 5 5
output:
264952
result:
ok single line: '264952'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4680kb
input:
2 7 855 2353 7986 5342 4395 3580 5540 3132 6 5 7 3 6 3 4 7 3 2 6 4 5 6 4 3 4 6 3 3 2 2 6 6 7 6 7 3 5 6 2 2 2 4 3 6 7 4 6 4 7 5 1 5 5 4 5 7 1 3 2 2 3 4 3 1 3 1 4 3 2 7 1 6 4 5 1 5 3 4 5 7 3 4 5 3 5 7 3 5 1 7 1 5 4 4 5 3 7 1 7 5 4 3 3 5 7 4 6 2 2 4 4 6 5 7 1 5 6 4 7 6 6 3 1 3 2 3 4 2 5 7 3 1 3 2 4 1 7...
output:
2043912
result:
ok single line: '2043912'
Test #22:
score: 0
Accepted
time: 1ms
memory: 4636kb
input:
1 7 944 7561 2934 5579 8659 4252 4768 7772 7 1 1 2 7 1 5 4 7 4 6 5 2 6 3 7 5 2 5 3 1 7 6 7 5 1 4 6 1 6 3 3 2 1 5 6 1 4 6 7 4 4 6 6 4 7 5 6 5 2 7 4 1 2 6 2 4 3 4 1 3 7 4 7 6 2 7 3 4 1 1 4 1 6 2 5 1 4 3 7 1 4 6 6 6 7 3 5 5 2 7 6 7 7 5 6 4 3 4 6 2 5 2 5 7 7 5 3 2 3 5 2 1 7 3 7 1 7 6 3 2 5 3 2 1 3 2 7 2...
output:
4815562
result:
ok single line: '4815562'
Test #23:
score: 0
Accepted
time: 0ms
memory: 4564kb
input:
1 7 472 3758 5759 6576 4652 6475 2334 2293 3 7 2 5 5 6 5 4 3 7 7 1 2 5 1 4 6 3 5 6 6 7 6 3 7 6 4 7 5 5 1 2 1 2 4 1 3 6 1 3 4 3 2 2 6 6 6 7 6 3 4 6 7 2 2 3 5 2 3 7 6 5 3 2 3 7 3 6 7 4 7 3 7 6 2 1 3 4 6 5 2 7 1 4 5 1 2 5 3 3 4 6 1 3 6 5 3 4 4 1 6 7 1 7 4 4 7 6 6 2 7 7 3 5 7 2 5 4 1 1 4 7 4 6 5 4 4 2 3...
output:
1856415
result:
ok single line: '1856415'
Test #24:
score: 0
Accepted
time: 1ms
memory: 4424kb
input:
2 6 147 4951 9586 7472 3436 3523 3963 6 4 1 4 3 4 3 4 5 5 6 5 2 6 5 2 5 3 6 2 1 2 1 1 6 4 2 2 4 3 4 2 1 3 1 1 4 3 1 2 5 6 6 4 1 3 1 5 2 5 6 1 3 1 4 6 5 1 4 6 5 6 3 2 1 4 5 3 3 4 3 6 3 5 5 5 4 4 3 2 1 5 2 4 6 2 6 3 5 1 3 1 1 1 4 3 1 3 3 5 5 3 4 2 2 2 5 4 3 2 6 2 2 1 1 6 5 4 4 4 2 1 6 6 4 6 1 4 1 5 3 ...
output:
376654
result:
ok single line: '376654'
Test #25:
score: 0
Accepted
time: 1ms
memory: 4540kb
input:
2 6 383 8626 3982 7035 8235 2240 1978 3 2 6 5 1 5 1 3 2 6 6 1 3 2 2 2 3 5 6 2 3 1 3 5 4 5 1 4 1 5 4 5 4 5 6 3 3 4 5 1 3 2 2 2 5 2 6 6 3 1 2 1 2 4 3 2 6 6 1 3 6 3 6 5 3 1 5 1 2 4 1 6 6 6 2 1 5 3 3 4 6 6 3 4 3 5 6 2 3 5 2 3 1 3 1 5 4 4 6 6 6 2 1 4 4 2 6 2 1 5 2 2 5 4 4 1 6 3 1 2 2 3 1 2 4 6 6 6 3 2 4 ...
output:
975131
result:
ok single line: '975131'
Test #26:
score: 0
Accepted
time: 2ms
memory: 4652kb
input:
3 10 1000 8463 1878 9586 5468 698 4386 9270 585 8803 5631 9 7 7 6 4 7 8 1 1 8 1 7 2 1 2 7 6 7 3 2 8 9 3 7 9 4 5 1 1 2 8 4 3 10 3 1 7 3 5 3 4 1 6 5 6 8 3 2 1 9 2 6 10 4 9 10 3 5 1 6 1 6 6 7 2 6 2 10 6 2 9 4 9 10 5 8 6 3 3 5 3 8 2 4 5 3 8 4 3 1 2 7 8 8 8 5 4 2 4 4 6 8 1 10 7 10 5 5 6 3 10 2 5 3 7 8 2 ...
output:
2260140
result:
ok single line: '2260140'
Test #27:
score: 0
Accepted
time: 2ms
memory: 4672kb
input:
3 10 1000 3686 7523 9745 8606 8188 2647 5529 6395 2289 1172 1 6 6 9 8 2 6 10 7 8 8 8 6 9 2 3 9 5 7 4 9 3 6 6 8 10 7 6 9 8 10 5 4 8 2 10 4 9 1 7 5 6 6 3 8 4 8 3 2 1 3 5 8 10 2 5 2 8 2 3 5 1 4 4 7 2 1 2 7 8 7 7 10 8 1 1 4 5 3 2 2 5 8 7 1 5 5 6 10 3 2 6 10 6 3 2 5 1 3 2 7 4 4 6 5 1 5 1 5 8 7 9 6 7 3 7 ...
output:
2518552
result:
ok single line: '2518552'
Test #28:
score: 0
Accepted
time: 2ms
memory: 4692kb
input:
3 10 1000 5110 7663 9311 977 2425 7918 5098 4738 9445 168 8 9 10 7 2 3 5 3 5 8 10 1 6 1 7 5 4 4 8 4 1 1 1 1 3 2 8 3 7 3 9 7 2 10 7 5 7 7 2 6 5 4 2 5 8 4 5 2 8 4 9 6 8 5 6 2 8 3 4 8 8 1 8 6 8 1 2 1 1 2 7 5 2 2 8 5 10 5 6 6 8 5 5 1 8 9 8 10 6 8 1 3 5 8 9 6 5 4 10 10 7 7 1 9 4 3 6 8 4 1 6 8 4 4 5 9 2 1...
output:
2290844
result:
ok single line: '2290844'
Test #29:
score: 0
Accepted
time: 0ms
memory: 4648kb
input:
3 10 1000 1385 4459 4489 6403 5915 3184 1602 3325 3959 7938 8 4 6 1 9 6 5 3 4 9 2 7 2 2 4 3 4 7 6 7 6 1 9 9 9 3 5 4 10 5 5 3 4 4 10 7 5 7 8 8 9 9 8 10 7 2 1 5 8 8 3 10 7 9 1 4 1 6 4 2 6 5 7 2 6 1 6 4 9 5 8 9 2 10 5 4 4 9 4 2 1 3 10 9 2 2 6 9 4 8 6 9 8 3 2 3 3 5 9 7 9 2 7 7 7 6 3 6 2 3 6 5 1 2 8 9 10...
output:
1839751
result:
ok single line: '1839751'
Test #30:
score: 0
Accepted
time: 2ms
memory: 4724kb
input:
3 10 1000 6563 8774 1869 9819 9442 9568 7985 3914 2048 682 8 3 2 6 5 2 10 5 8 10 1 6 4 4 7 10 10 1 5 2 2 2 8 8 7 2 1 7 7 2 1 2 4 6 9 5 9 10 8 10 7 7 8 10 2 3 3 3 8 3 7 2 4 3 9 1 1 3 8 8 4 4 3 10 9 1 1 5 6 3 9 7 8 1 1 2 9 8 9 10 4 6 5 2 1 8 6 7 3 1 5 3 8 4 3 6 1 2 4 2 3 6 1 9 9 3 1 7 9 8 5 7 2 4 10 4...
output:
2657807
result:
ok single line: '2657807'
Test #31:
score: 0
Accepted
time: 2ms
memory: 4688kb
input:
3 10 1000 7524 4984 1721 7555 1973 5054 1073 1459 707 9989 7 7 3 1 4 6 3 2 1 6 7 3 9 4 6 10 7 9 4 2 4 4 5 10 3 7 5 7 1 6 4 7 4 1 5 5 1 9 6 1 9 4 5 9 3 1 9 7 3 2 9 3 7 6 8 8 2 2 6 9 10 6 3 9 4 8 1 5 10 4 8 9 8 4 4 7 5 5 9 8 6 5 6 6 3 8 4 1 5 3 6 2 4 8 10 10 3 7 4 8 1 4 3 3 10 3 4 8 5 10 10 2 3 8 9 1 ...
output:
1615277
result:
ok single line: '1615277'
Test #32:
score: 0
Accepted
time: 2ms
memory: 4704kb
input:
3 10 1000 3699 7245 1226 7369 7999 3022 6830 9052 6983 1666 7 5 9 3 6 10 3 6 8 5 7 10 1 7 3 8 6 6 1 2 1 9 4 3 1 3 1 2 5 3 6 4 10 4 8 9 1 9 1 6 5 4 6 7 7 3 9 8 5 7 9 4 5 7 7 8 9 9 8 5 7 6 1 5 5 7 9 5 7 6 3 2 6 4 7 8 6 4 10 1 9 5 9 6 3 2 8 1 2 3 4 8 9 4 2 5 3 8 2 9 9 6 4 8 5 7 9 1 1 4 5 9 10 10 5 6 10...
output:
2431479
result:
ok single line: '2431479'
Test #33:
score: 0
Accepted
time: 0ms
memory: 4664kb
input:
3 10 1000 8093 5887 665 9335 6022 6794 8782 4583 2677 9405 9 6 9 1 9 9 5 7 7 9 9 2 2 9 5 9 3 9 4 6 8 7 9 2 5 4 1 2 6 5 6 5 4 2 3 7 9 6 2 2 6 7 10 10 2 9 1 10 9 8 5 2 5 6 10 1 9 5 9 3 5 10 9 6 4 1 6 2 2 7 9 10 8 1 6 6 4 6 4 8 2 10 1 4 7 8 10 7 9 7 9 9 5 1 3 3 7 8 7 5 6 2 2 7 8 7 10 10 3 7 9 10 10 2 9...
output:
2725603
result:
ok single line: '2725603'
Test #34:
score: 0
Accepted
time: 2ms
memory: 4716kb
input:
3 10 1000 1382 950 7116 3008 4636 9147 7781 9307 4202 3980 3 7 1 1 10 7 9 6 2 4 10 3 5 6 2 8 8 6 6 5 1 1 3 10 6 1 10 4 4 10 3 1 6 4 2 1 9 9 10 2 6 4 8 10 8 7 3 2 4 10 4 4 10 2 4 1 5 1 5 3 4 7 10 2 10 2 1 4 2 1 4 10 2 3 8 2 9 8 4 6 9 3 7 10 6 4 4 2 9 3 4 10 1 8 9 4 1 3 4 10 7 5 10 10 7 10 2 5 5 10 3 ...
output:
2087368
result:
ok single line: '2087368'
Test #35:
score: 0
Accepted
time: 2ms
memory: 4740kb
input:
3 10 1000 5575 5894 6041 8624 4145 430 5289 3048 283 8915 8 4 1 6 10 8 6 4 9 5 9 1 10 2 4 8 5 9 10 2 4 5 2 8 7 1 8 1 4 8 10 1 8 1 8 7 2 8 6 4 7 3 9 5 5 9 10 7 2 1 7 4 7 2 8 6 6 5 9 5 10 6 5 4 4 7 2 8 4 7 7 1 1 5 2 8 4 3 2 8 10 9 3 1 2 8 1 10 3 1 2 3 8 4 9 4 7 4 5 9 5 7 7 8 8 7 4 2 8 5 3 6 8 9 3 8 4 ...
output:
2093790
result:
ok single line: '2093790'
Test #36:
score: 0
Accepted
time: 22ms
memory: 7232kb
input:
10 10 10000 4954 8578 3562 8711 381 3244 4814 3367 2347 5956 5 7 8 10 9 9 7 10 7 7 8 1 5 7 5 9 2 8 9 5 4 10 10 8 1 5 10 10 8 3 3 8 5 4 2 10 3 8 3 7 7 10 3 5 7 4 5 4 2 3 2 3 4 7 2 2 10 5 8 2 9 5 4 3 4 5 10 2 8 2 2 6 7 10 8 9 2 3 10 1 7 3 8 4 4 7 2 6 10 3 3 3 3 10 10 1 6 7 7 5 7 10 7 5 5 6 9 2 10 10 4...
output:
45914
result:
ok single line: '45914'
Test #37:
score: 0
Accepted
time: 25ms
memory: 7256kb
input:
10 100 10000 7865 1307 5608 5416 4308 2170 1279 1106 3644 8967 9764 1580 8548 7472 7594 7897 7493 9116 1847 344 99 4486 9552 4942 6209 9216 6231 7034 8143 9802 3636 6671 249 467 2919 774 2881 2507 7119 8370 7575 9168 1543 3459 4632 3381 6488 78 7008 5136 5566 3785 805 3276 8715 1778 9301 1880 9713 3...
output:
30873149
result:
ok single line: '30873149'
Test #38:
score: 0
Accepted
time: 22ms
memory: 7184kb
input:
10 1000 10000 3327 5360 2960 1390 9315 8751 2691 5412 2231 7628 6526 5732 3437 7211 1640 4766 934 6486 3468 3511 2202 1489 3276 1537 657 2920 5944 8752 9141 2425 3906 4261 6971 6610 873 2135 9903 5714 7414 3838 5109 1602 4780 1346 8742 4942 9410 6792 9282 2754 9724 7686 84 9434 3990 4083 3828 1939 8...
output:
42320546
result:
ok single line: '42320546'
Test #39:
score: 0
Accepted
time: 27ms
memory: 7140kb
input:
10 10000 10000 4645 5891 1287 51 6153 2463 6953 5809 4558 1380 9741 3661 6934 3005 4680 8754 1949 8237 7131 6830 1317 700 2298 2253 1208 9419 8294 5282 8910 518 3465 5375 8165 2363 8584 5666 4553 9189 1641 8160 1756 2413 8490 78 2818 398 2743 6473 9266 6728 9181 3429 8286 5908 8991 872 2759 4633 640...
output:
47288172
result:
ok single line: '47288172'
Test #40:
score: 0
Accepted
time: 23ms
memory: 7076kb
input:
9 10 9493 6886 4700 1472 6714 7832 8893 5523 4637 3638 3667 9 6 10 2 2 4 6 6 5 4 3 5 9 5 8 3 2 8 1 5 1 9 10 3 4 10 10 9 7 6 3 1 3 2 7 5 4 6 2 8 10 2 9 3 7 9 8 2 7 9 6 5 9 9 8 9 8 1 10 1 10 8 6 3 9 7 3 5 2 5 7 6 9 4 6 3 10 2 4 8 7 1 7 8 8 5 10 5 8 7 1 2 2 6 6 8 7 6 1 10 1 1 6 2 6 10 9 4 1 9 2 1 7 8 5...
output:
1393211
result:
ok single line: '1393211'
Test #41:
score: 0
Accepted
time: 13ms
memory: 7164kb
input:
4 98 9584 3775 7230 7571 3052 4921 358 6156 3911 1541 5659 2082 6954 8281 8801 5578 7518 5163 4107 257 2649 3612 5888 8110 8625 6318 4518 5370 7407 7230 8636 2535 6700 7435 5908 2929 9937 5790 2028 2873 1340 2150 5778 2914 5412 8824 8765 8366 1447 1096 6841 937 5170 6778 6531 7953 9344 7719 2815 602...
output:
37555103
result:
ok single line: '37555103'
Test #42:
score: 0
Accepted
time: 23ms
memory: 7216kb
input:
9 931 9983 6325 9787 6903 2965 7104 3483 9161 5198 5563 8368 3281 4334 2728 9927 1405 9343 7051 7310 910 14 8258 5396 6861 4883 4678 6547 4688 4165 597 5400 4017 545 7637 9828 873 3907 3526 6129 1229 2778 888 4663 8653 747 1960 5759 77 8756 1334 3843 726 2353 9963 3101 8983 2996 2162 8878 7147 3393 ...
output:
42558090
result:
ok single line: '42558090'
Test #43:
score: 0
Accepted
time: 13ms
memory: 7012kb
input:
4 9805 9566 5400 4238 2083 8833 9229 5402 6107 2064 9708 6983 3677 2157 9828 9680 4394 9882 2361 2368 1190 9439 3349 814 5530 4870 5715 9532 4909 882 1084 1054 8842 9783 8959 2533 9081 1674 4927 3223 6626 9660 7690 6929 5395 3190 7609 4089 8327 33 1659 4222 8065 9670 3459 6609 8250 2797 7083 7707 65...
output:
46475715
result:
ok single line: '46475715'
Test #44:
score: 0
Accepted
time: 22ms
memory: 7036kb
input:
9 9 9318 4153 3972 6156 3057 8674 8993 5145 7313 3538 8 2 8 9 6 5 4 6 3 8 4 4 2 5 3 4 1 7 1 5 8 1 5 9 8 7 8 9 3 9 5 9 8 5 9 7 6 5 8 2 2 5 5 4 5 3 9 7 8 4 2 3 9 2 9 2 6 3 4 4 8 2 8 6 7 7 5 2 2 5 4 2 1 3 4 9 5 2 1 9 6 4 1 4 8 9 5 5 3 4 1 4 7 2 8 3 1 1 9 5 7 4 4 6 9 7 4 6 9 6 7 4 9 8 3 3 7 1 6 9 5 3 7 ...
output:
51001
result:
ok single line: '51001'
Test #45:
score: 0
Accepted
time: 10ms
memory: 7236kb
input:
3 95 9810 1516 9429 6830 802 7439 8830 2763 6893 469 2462 6343 38 6470 8837 5079 1378 5421 9976 5905 6729 5695 6349 9583 1059 2612 3278 7704 6601 9287 547 2453 6978 7112 6800 7987 8766 4782 5709 8828 7214 4078 4912 1833 1900 4081 5624 8513 6717 3971 9455 6442 1704 2763 5494 6443 5540 2437 6287 6601 ...
output:
41206637
result:
ok single line: '41206637'
Test #46:
score: 0
Accepted
time: 19ms
memory: 7216kb
input:
6 971 9922 2724 4693 8477 524 2654 8722 7765 1231 9357 541 4175 9935 1572 8978 7650 8990 6034 3420 2271 7021 2532 2833 2861 939 5293 6029 2779 7802 7759 8842 3885 36 9902 4375 3568 1444 6650 1566 1727 547 7729 6393 6418 1635 863 835 4335 7159 8390 6682 9807 2215 2907 7196 5508 8994 5975 2142 2842 80...
output:
47372597
result:
ok single line: '47372597'
Test #47:
score: 0
Accepted
time: 17ms
memory: 7048kb
input:
9 9727 9594 7986 2325 2140 2727 1394 4550 4528 5445 5512 2766 3828 372 7215 883 2391 1049 174 645 422 3538 6028 5465 651 1340 7062 6814 6724 2937 2090 9637 1305 8595 9083 6955 390 7136 3197 1218 4614 4565 6753 8811 7001 3589 4284 7948 7148 8875 3887 5167 1016 2903 8856 9894 3683 5492 1023 2590 5879 ...
output:
46321281
result:
ok single line: '46321281'
Test #48:
score: 0
Accepted
time: 0ms
memory: 4476kb
input:
6 95 80 9062 4199 7793 1825 4092 5101 9952 9438 3096 5115 8095 8095 3541 1728 3624 5405 1931 5767 8624 4221 771 7861 5812 4588 1471 9223 1922 3087 8568 7409 1645 7084 8804 4819 8166 5340 2698 5113 7836 3891 8000 216 9658 7714 5327 1848 2561 8976 8218 6845 291 6340 999 4739 7164 110 2315 9631 5649 26...
output:
327865
result:
ok single line: '327865'
Test #49:
score: 0
Accepted
time: 1ms
memory: 4392kb
input:
3 3 78 9031 4177 2405 2 1 1 3 3 3 3 2 2 1 1 1 3 2 1 3 1 3 2 2 2 3 3 3 2 1 3 3 1 1 3 1 1 2 3 3 2 2 3 3 2 2 3 3 2 1 2 1 1 2 1 1 1 3 1 2 3 2 1 3 3 1 2 1 2 3 2 3 3 1 3 3 1 3 3 1 1 2
output:
15613
result:
ok single line: '15613'
Test #50:
score: 0
Accepted
time: 1ms
memory: 4396kb
input:
5 82 79 3301 3085 3629 7513 7287 2476 5067 8604 9667 1270 6292 9808 4710 4972 5442 585 7425 5071 550 6705 9739 4886 3300 1792 3595 9333 1082 3952 1796 5064 8317 3309 4819 7400 5112 5941 9716 8352 7767 4614 2513 5166 997 8316 1435 5823 1011 4515 7631 4712 3173 3871 3958 1244 2496 9677 624 2938 2469 7...
output:
294286
result:
ok single line: '294286'
Test #51:
score: 0
Accepted
time: 1ms
memory: 4356kb
input:
10 98 35 9569 9074 9554 8497 3779 1492 1663 8785 2065 4736 646 3726 8229 2718 5139 4757 5857 1732 6288 7580 4748 775 4681 7979 4882 1516 2474 1216 4334 4052 2606 4259 2913 7415 8806 32 4077 1711 3100 4363 5154 5533 8881 414 4810 8552 9752 3527 1982 6728 1374 7748 9755 6087 9713 8630 4109 7672 7910 3...
output:
186008
result:
ok single line: '186008'
Test #52:
score: 0
Accepted
time: 1ms
memory: 4388kb
input:
1 68 87 5113 8233 9162 7102 2189 471 923 1406 6338 1298 6977 2634 9658 8216 8921 4679 7578 8644 5591 3881 4405 1650 5974 6569 9106 6945 9276 2435 1609 1300 135 5302 8821 6018 5895 1277 7489 2520 4486 1694 2441 6772 109 6156 7570 8814 6229 4317 7505 2626 5371 9274 1452 4391 5250 8739 6912 4463 292 57...
output:
428456
result:
ok single line: '428456'
Test #53:
score: 0
Accepted
time: 0ms
memory: 4472kb
input:
8 10 73 7972 6837 6003 9484 4506 5451 9109 7776 6540 9206 5 7 1 9 6 10 2 3 7 4 2 1 9 3 10 6 2 2 9 9 1 5 2 8 9 7 2 7 3 1 1 2 4 2 4 6 9 4 6 3 3 9 7 1 6 3 1 1 1 4 10 10 9 1 5 2 5 2 7 5 1 2 3 1 1 2 9 1 9 8 9 2 1
output:
91102
result:
ok single line: '91102'
Test #54:
score: 0
Accepted
time: 1ms
memory: 4368kb
input:
9 57 69 591 1258 4404 3053 274 3467 6211 1160 8299 8411 2192 1342 3156 4354 5535 5290 8258 1564 5996 4268 3814 4982 3183 2226 8456 3900 9786 7761 4999 8362 2864 8014 5039 444 9810 3911 8857 4304 1182 2773 7190 4817 7305 1691 7295 7883 8093 1963 9974 7377 7662 1670 8437 7994 4079 764 6470 35 51 6 30 ...
output:
217710
result:
ok single line: '217710'
Test #55:
score: 0
Accepted
time: 1ms
memory: 4360kb
input:
6 1 78 5896 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
5896
result:
ok single line: '5896'
Test #56:
score: 0
Accepted
time: 1ms
memory: 4352kb
input:
8 38 27 8665 7084 3282 8870 3495 9238 754 1923 3193 8936 2402 6444 3164 5491 8276 4523 3531 1879 1801 66 3351 378 3154 3446 6546 4164 6545 3131 3030 5918 6379 2383 9876 9629 5921 9176 2829 4215 27 17 18 27 36 22 35 26 19 15 8 5 1 34 34 38 32 8 2 11 23 28 15 9 2 36 12
output:
97389
result:
ok single line: '97389'
Test #57:
score: 0
Accepted
time: 1ms
memory: 4424kb
input:
3 85 44 6968 7440 2630 6429 6171 7721 5879 5376 6873 1878 4939 7435 5531 186 6250 8185 3024 5997 7702 8554 3841 7927 639 4767 2795 4894 2870 9010 9055 6880 6873 5846 8105 7737 7319 4014 6329 6367 995 518 2217 9622 6817 187 3346 2830 7201 2128 2168 7963 6168 1323 8106 4656 3231 5688 6674 3627 6717 63...
output:
188974
result:
ok single line: '188974'
Test #58:
score: 0
Accepted
time: 0ms
memory: 4428kb
input:
1 24 7 1839 7829 6555 3069 6772 7326 1820 6707 3250 6025 2684 2885 6825 5309 5931 9517 2239 8152 9594 6111 957 4150 8425 40 6 15 5 20 14 5 20
output:
44332
result:
ok single line: '44332'
Test #59:
score: 0
Accepted
time: 0ms
memory: 4484kb
input:
9 85 99 3852 5283 6340 3257 4821 9906 5916 3937 9339 7839 7743 5875 8197 3475 3206 7575 2514 2860 5685 6325 725 3082 5444 9420 2380 2862 3178 1870 9397 4468 291 6088 8286 2226 229 5975 3335 8434 7952 4834 5813 2302 8408 5335 2876 6389 996 9973 5514 87 2606 8426 3624 1760 5498 6955 3296 8096 6765 363...
output:
331307
result:
ok single line: '331307'
Test #60:
score: 0
Accepted
time: 1ms
memory: 4392kb
input:
7 18 99 2406 1503 1379 778 5959 7188 5853 5488 3694 9238 3682 2815 9232 1216 662 1717 6505 4000 7 9 9 8 18 4 2 17 6 14 2 6 8 10 8 18 7 5 17 4 5 13 5 14 18 13 7 1 14 1 4 5 5 14 9 13 7 6 3 13 3 5 15 18 14 12 7 10 3 6 8 8 15 4 13 12 9 6 1 14 6 7 13 6 3 13 1 10 3 13 12 6 16 8 17 10 15 17 6 11 14 15 2 2 ...
output:
115469
result:
ok single line: '115469'
Test #61:
score: 0
Accepted
time: 1ms
memory: 4492kb
input:
6 51 72 474 6563 6045 3317 4682 8723 496 9915 214 596 9162 274 5048 4636 677 1626 809 2701 3517 9729 4198 4608 9322 8141 2270 8710 1132 3059 55 9796 1095 4093 681 5516 4705 4034 4012 5933 8244 8392 8042 2415 9633 3462 4522 7611 9889 4555 9185 6790 3232 48 19 46 37 46 25 23 13 6 15 37 32 4 24 5 3 3 3...
output:
229110
result:
ok single line: '229110'
Test #62:
score: 0
Accepted
time: 1ms
memory: 4348kb
input:
1 43 100 9645 2313 8016 335 5111 9961 8864 1686 4629 7044 3713 7837 8753 7338 614 3848 8169 3384 4831 7767 7316 8601 9641 5675 5712 5031 6083 1875 881 2745 9038 7819 7071 4684 314 1639 8870 4552 7452 7061 1299 8125 8223 18 10 22 36 32 38 40 4 33 1 42 31 19 18 18 39 31 9 34 2 7 20 41 38 39 38 36 30 2...
output:
561803
result:
ok single line: '561803'
Test #63:
score: 0
Accepted
time: 1ms
memory: 4428kb
input:
10 66 82 9945 7762 4805 2786 3380 2838 9403 4659 9140 6392 9362 3758 8255 2510 5292 9897 9526 7448 6227 4251 4175 6929 1254 4612 8445 7289 4616 4941 5214 3290 6794 4529 210 630 5653 3298 3483 6915 8400 6471 6753 3954 9431 8873 5732 9 6262 3544 3223 6371 5304 6191 4683 9044 4145 9396 9431 3131 9030 6...
output:
311378
result:
ok single line: '311378'
Test #64:
score: 0
Accepted
time: 1ms
memory: 4456kb
input:
10 22 99 532 7334 7332 7301 1945 4777 8349 2662 1911 1984 5788 2224 9985 7481 2274 4865 5886 7699 3654 7706 429 7672 1 18 20 6 21 17 12 17 4 18 20 19 6 20 9 12 15 21 10 21 11 9 5 7 11 3 21 15 3 12 12 19 4 9 8 12 13 17 11 19 17 10 19 11 8 2 1 19 16 14 10 9 9 19 6 6 17 5 19 16 19 1 11 9 22 10 16 9 5 4...
output:
152315
result:
ok single line: '152315'
Test #65:
score: 0
Accepted
time: 0ms
memory: 4384kb
input:
6 4 71 8856 6630 4905 188 2 4 1 1 2 4 3 4 2 2 3 2 2 4 4 3 2 3 4 4 2 4 2 4 2 4 2 3 4 4 4 3 3 2 4 1 1 2 3 2 4 2 4 4 3 2 1 2 4 1 3 4 2 2 1 4 1 2 4 3 1 2 3 4 1 1 4 2 4 4 1
output:
20579
result:
ok single line: '20579'
Test #66:
score: 0
Accepted
time: 1ms
memory: 4364kb
input:
4 53 15 7744 3202 9498 6019 8976 376 5435 3147 3018 6611 4503 4148 7280 8419 8311 7042 3785 7055 8142 7282 5329 6592 7177 2837 6175 9116 8892 4477 3863 1226 3226 1232 9955 6900 3957 7589 6849 5662 8044 8616 837 1824 7878 5919 8975 763 8548 4149 3374 6648 1909 7427 8674 53 45 47 6 13 6 19 31 18 25 11...
output:
90422
result:
ok single line: '90422'
Test #67:
score: 0
Accepted
time: 0ms
memory: 4384kb
input:
5 83 40 8269 154 6911 6408 4574 7657 392 9693 6211 5061 2368 4922 8566 8660 6176 4221 7519 5674 9220 2539 2936 301 8381 2182 639 7601 6907 1583 2997 2848 2286 8582 2145 8714 1813 6026 2900 1479 7969 7696 2225 264 4843 2522 2744 4938 672 6917 7869 2294 2834 4475 6541 2328 4527 5870 6143 559 6815 1066...
output:
144985
result:
ok single line: '144985'