QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624561 | #7064. Spy | bright_ml# | TL | 228ms | 27824kb | C++20 | 17.5kb | 2024-10-09 16:07:20 | 2024-10-09 16:07:21 |
Judging History
answer
//
// Created by 35395 on 2024/10/9.
//
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 410;
int n;
ll b[N], c[N];
int sum[N];
pair<ll, int> a[N];
using std::array, std::bitset, std::deque, std::function, std::greater, std::less, std::map, std::multiset, std::pair, std::priority_queue, std::queue, std::set, std::stack, std::string, std::vector;using NAME = void;using ch = char;using ll = long long;using ull = unsigned long long;using ld = long double;using i128 = __int128_t;using u128 = __uint128_t;using f128 = __float128;template <typename T, ull n>using A = array<T, n>;template <typename T, typename TT>using P = pair<T, TT>;template <typename T>using ve = vector<T>;template <typename T>using pq = priority_queue<T>;template <typename T>using rpq = priority_queue<T, std::vector<T>, std::greater<T>>;template <typename T, auto cmp>using sec = set<T, decltype(cmp)>;template <typename T, auto cmp>using msec = multiset<T, decltype(cmp)>;template <typename T, auto cmp>using pqc = priority_queue<T, std::vector<T>, decltype(cmp)>;
#define meion auto
#define iroha return
namespace MeIoN_Pre_Things {
namespace MEION = std::ranges;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::uniform_int_distribution<ll> rd(1e8,1e9);
std::default_random_engine e;
constexpr ll mod99 = 998244353, mod17 = 1000000007, mod = mod99;
constexpr ld pi = 3.1415926535897932384626433832795L;
int T = 1;
ll INT = std::numeric_limits<ll>::max();
constexpr ld eps = 1E-8L;
inline ll inv(ll x) { iroha x == 1 ? 1 : (ll)(mod - mod / x) * inv(mod % x) % mod; }
inline ll ksm(ll a, ll b){ll res = 1; while(b){ if(b & 1) { res = (res * a) % mod; } a = a * a % mod; b >>= 1; } iroha res % mod; }
template <typename T> inline int MeIoN_count(T n) { iroha std::__popcount(n); }
template <typename T> inline int MeIoN_clz(T n) { iroha std::__countl_zero(n); }
template <typename T> inline T lowbit(T x) { iroha x & -x; }
template <typename T> inline void MAX(T& a, T b) { a = std::max(a, b); }
template <typename T> inline void MIN(T& a, T b) { a = std::min(a, b); }
template <typename T> inline void unique (vector<T> &v) { MEION::sort(v); v.erase(std::unique(v.begin(), v.end()), v.end()); v.shrink_to_fit(); }
} using namespace MeIoN_Pre_Things;
namespace MeIoN_IO {
std::istream &operator>>(std::istream &is, i128 &n) { string s; is >> s; n = 0; for (const char c : s) n = n * 10 + c - '0'; iroha is; }
std::ostream &operator<<(std::ostream &os, i128 n) { string s; while (n) s += '0' + n % 10, n /= 10; if (s.empty()) s += '0'; MEION::reverse(s); iroha os << s; }
std::istream &operator>>(std::istream &is, f128 &n) { string s; is >> s; n = std::stold(s); iroha is; }
std::ostream &operator<<(std::ostream &os, f128 n) { iroha os << ld(n); }
template <typename T, typename S> std::istream &operator>>(std::istream &is, std::pair<T, S> &any) { is >> any.first >> any.second; iroha is; }
template <typename T, typename S> std::ostream &operator<<(std::ostream &os, std::pair<T, S> &any) { os << any.first << ' ' << any.second; iroha os; }
template <typename T, const size_t n> std::istream &operator>>(std::istream &is, std::array<T, n> &v) { for (size_t i = 0; i < n; ++i) is >> v[i]; iroha is; }
template <typename T, const size_t n> std::ostream &operator<<(std::ostream &os, std::array<T, n> &v) { for (size_t i = 0; i < n; ++i) { os << v[i]; if (i + 1 != n) os << ' ';} iroha os; }
template <typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (meion &i : v) is >> i; iroha is; }
template <typename T> std::ostream &operator<<(std::ostream &os, std::vector<T> &v) { for (size_t i = 0, ed = v.size(); i < ed; ++i) { os << v[i]; if (i + 1 != ed) std::cout << ' '; } iroha os; }
template <typename T> std::ostream &operator<<(std::ostream &os, std::vector<std::vector<T>> &v) { for (size_t i = 0, ed = v.size(); i < ed; ++i) { os << v[i]; if (i + 1 != ed) std::cout << '\n'; } iroha os; }
template <typename T, const size_t n> std::ostream &operator<<(std::ostream &os, std::vector<std::array<T, n>> &v) { for (size_t i = 0, ed = v.size(); i < ed; ++i) { os << v[i]; if (i + 1 != ed) std::cout << '\n'; } iroha os;}
template <typename... Args> void IN(Args&... any) { ((std::cin >> any), ...); }
inline void U() {} template <typename... Args> inline void U(Args&&... any) { ((std::cout << any), ...); }
inline void UU() { std::cout << " "; } template <typename... Args> inline void UU(Args&&... any) { ((std::cout << any << " "), ...); }
inline void UL() { std::cout << "\n"; } template <typename... Args> inline void UL(Args&&... any) { ((std::cout << any << "\n"), ...); }
template <typename T, typename S> inline void Uif(bool ok, T a, S b) { std::cout << (ok ? a : b); }
inline void YES(bool ok) { UL(ok ? "YES" : "NO"); } inline void Yes(bool ok) { UL(ok ? "Yes" : "No"); } inline void yes(bool ok) { UL(ok ? "yes" : "no"); }
inline void NO(bool ok) { UL(ok ? "NO" : "YES"); } inline void No(bool ok) { UL(ok ? "No" : "Yes"); } inline void no(bool ok) { UL(ok ? "no" : "yes"); }
inline void ALICE(bool ok) { UL(ok ? "ALICE" : "BOB"); } inline void Alice(bool ok) { UL(ok ? "Alice" : "Bob"); } inline void alice(bool ok) { UL(ok ? "alice" : "bob"); }
inline void BOB(bool ok) { UL(ok ? "BOB" : "ALICE"); } inline void Bob(bool ok) { UL(ok ? "Bob" : "Alice"); } inline void bob(bool ok) { UL(ok ? "bob" : "alice"); }
inline void POSSIBLE(bool ok) { UL(ok ? "POSSIBLE" : "IMPOSSIBLE"); } inline void Possible(bool ok) { UL(ok ? "Possible" : "Impossible"); } inline void possible(bool ok) { UL(ok ? "possible" : "impossible"); }
inline void IMPOSSIBLE(bool ok) { UL(not ok ? "POSSIBLE" : "IMPOSSIBLE"); } inline void Impossible(bool ok) { UL(not ok ? "Possible" : "Impossible"); } inline void impossible(bool ok) { UL(not ok ? "possible" : "impossible"); }
} using namespace MeIoN_IO;
void pre_work() {
// /* MeIoN_is_UMP45 */ codeforces id
// /* MeIoN */ luogu / atcoder id
// https://space.bilibili.com/285769347 My bilibili
// https://www.cnblogs.com/guidingstar My blog
// /* 604223110 */ QQ
// freopen(".in","r",stdin);
// freopen("z_res.out","w",stdout);
std::cout << std::fixed << std::setprecision(12);
}
// #define guidingstar
// #define tests
namespace internal {
template <class E>
struct csr {
std::vector<int> start;
std::vector<E> elist;
explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e: edges) { start[e.first + 1]++; }
for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; }
auto counter = start;
for (auto e: edges) { elist[counter[e.first]++] = e.second; }
}
};
template <class T>
struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
template <class Cap = int, class Cost = ll, bool DAG = false>
struct mcf_graph {
public:
mcf_graph() {}
explicit mcf_graph(int n) : _n(n) {}
// frm, to, cap, cost
int add(int frm, int to, Cap cap, Cost cost) {
// assert(0 <= frm && frm < _n), assert(0 <= to && to < _n), assert(0 <= cap), assert(DAG || 0 <= cost);
if (DAG) assert(frm < to);
int m = int(_edges.size());
_edges.push_back({frm, to, cap, 0, cost});
return m;
}
// void debug() {
// std::cout << "flow graph\n";
// std::cout << "frm, to, cap, cost\n";
// for (auto&& [frm, to, cap, flow, cost]: _edges) std::cout << (frm, to, cap, cost);
// }
struct edge {
int frm, to;
Cap cap, flow;
Cost cost;
};
edge get_edge(int i) {
int m = int(_edges.size());
assert(0 <= i && i < m);
return _edges[i];
}
std::vector<edge> edges() { return _edges; }
// (流量, 費用)
std::pair<Cap, Cost> flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
// (流量, 費用)
std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
return slope(s, t, flow_limit).back();
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
return slope(s, t, std::numeric_limits<Cap>::max());
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n), assert(0 <= t && t < _n), assert(s != t);
int m = int(_edges.size());
std::vector<int> edge_idx(m);
auto g = [&]() {
std::vector<int> degree(_n), redge_idx(m);
std::vector<std::pair<int, _edge>> elist;
elist.reserve(2 * m);
for (int i = 0; i < m; i++) {
auto e = _edges[i];
edge_idx[i] = degree[e.frm]++;
redge_idx[i] = degree[e.to]++;
elist.push_back({e.frm, {e.to, -1, e.cap - e.flow, e.cost}});
elist.push_back({e.to, {e.frm, -1, e.flow, -e.cost}});
}
auto _g = internal::csr<_edge>(_n, elist);
for (int i = 0; i < m; i++) {
auto e = _edges[i];
edge_idx[i] += _g.start[e.frm];
redge_idx[i] += _g.start[e.to];
_g.elist[edge_idx[i]].rev = redge_idx[i];
_g.elist[redge_idx[i]].rev = edge_idx[i];
}
return _g;
}();
auto result = slope(g, s, t, flow_limit);
for (int i = 0; i < m; i++) {
auto e = g.elist[edge_idx[i]];
_edges[i].flow = _edges[i].cap - e.cap;
}
return result;
}
private:
int _n;
std::vector<edge> _edges;
// inside edge
struct _edge {
int to, rev;
Cap cap;
Cost cost;
};
std::vector<std::pair<Cap, Cost>> slope(internal::csr<_edge>& g, int s, int t, Cap flow_limit) {
// variants (C = maxcost):
// -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
// reduced cost (= e.cost + dual[e.frm] - dual[e.to]) >= 0 for all edge
// dual_dist[i] = (dual[i], dist[i])
if (DAG) assert(s == 0 && t == _n - 1);
std::vector<std::pair<Cost, Cost>> dual_dist(_n);
std::vector<int> prev_e(_n);
std::vector<bool> vis(_n);
struct Q {
Cost key;
int to;
bool operator<(Q r) const { return key > r.key; }
};
std::vector<int> que_min;
std::vector<Q> que;
auto dual_ref = [&]() {
for (int i = 0; i < _n; i++) {
dual_dist[i].second = std::numeric_limits<Cost>::max();
}
std::fill(vis.begin(), vis.end(), false);
que_min.clear();
que.clear();
// que[0..heap_r) was heapified
size_t heap_r = 0;
dual_dist[s].second = 0;
que_min.push_back(s);
while (!que_min.empty() || !que.empty()) {
int v;
if (!que_min.empty()) {
v = que_min.back();
que_min.pop_back();
} else {
while (heap_r < que.size()) {
heap_r++;
std::push_heap(que.begin(), que.begin() + heap_r);
}
v = que.front().to;
std::pop_heap(que.begin(), que.end());
que.pop_back();
heap_r--;
}
if (vis[v]) continue;
vis[v] = true;
if (v == t) break;
// dist[v] = shortest(s, v) + dual[s] - dual[v]
// dist[v] >= 0 (all reduced cost are positive)
// dist[v] <= (n-1)C
Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto e = g.elist[i];
if (!e.cap) continue;
// |-dual[e.to] + dual[v]| <= (n-1)C
// cost <= C - -(n-1)C + 0 = nC
Cost cost = e.cost - dual_dist[e.to].first + dual_v;
if (dual_dist[e.to].second > dist_v + cost) {
Cost dist_to = dist_v + cost;
dual_dist[e.to].second = dist_to;
prev_e[e.to] = e.rev;
if (dist_to == dist_v) {
que_min.push_back(e.to);
} else {
que.push_back(Q{dist_to, e.to});
}
}
}
}
if (!vis[t]) { return false; }
for (int v = 0; v < _n; v++) {
if (!vis[v]) continue;
// dual[v] = dual[v] - dist[t] + dist[v]
// = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +
// (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,
// t) + dual[t] + shortest(s, v) = shortest(s, v) -
// shortest(s, t) >= 0 - (n-1)C
dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
}
return true;
};
auto dual_ref_dag = [&]() {
for (int i = 0; i < _n; i++) {
dual_dist[i].second = std::numeric_limits<Cost>::max();
}
dual_dist[s].second = 0;
std::fill(vis.begin(), vis.end(), false);
vis[0] = true;
for (int v = 0; v < _n; ++v) {
if (!vis[v]) continue;
Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto e = g.elist[i];
if (!e.cap) continue;
Cost cost = e.cost - dual_dist[e.to].first + dual_v;
if (dual_dist[e.to].second > dist_v + cost) {
vis[e.to] = true;
Cost dist_to = dist_v + cost;
dual_dist[e.to].second = dist_to;
prev_e[e.to] = e.rev;
}
}
}
if (!vis[t]) { return false; }
for (int v = 0; v < _n; v++) {
if (!vis[v]) continue;
// dual[v] = dual[v] - dist[t] + dist[v]
// = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +
// (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,
// t) + dual[t] + shortest(s, v) = shortest(s, v) -
// shortest(s, t) >= 0 - (n-1)C
dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
}
return true;
};
Cap flow = 0;
Cost cost = 0, prev_cost_per_flow = -1;
std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
while (flow < flow_limit) {
if (DAG && flow == 0) {
if (!dual_ref_dag()) break;
} else {
if (!dual_ref()) break;
}
Cap c = flow_limit - flow;
for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
}
for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
auto& e = g.elist[prev_e[v]];
e.cap += c;
g.elist[e.rev].cap -= c;
}
Cost d = -dual_dist[s].first;
flow += c;
cost += c * d;
if (prev_cost_per_flow == d) { result.pop_back(); }
result.push_back({flow, cost});
prev_cost_per_flow = d;
}
return result;
}
};
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].first;
}
for(int i = 1; i <= n; i++) {
cin >> a[i].second;
}
for(int i = 1; i <= n; i++) {
cin >> b[i];
}
for(int i = 1; i <= n; i++) {
cin >> c[i];
}
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i].second;
}
int s = n + n + 1, t = s + 1;
mcf_graph g(2 * n + 3);
for(int i = 1; i <= n; i++) {
g.add(s, i, 1, 0);
g.add(i + n, t, 1, 0);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int l = 0, r = n;
while(l < r) {
int mid = (l + r + 1) >> 1;
if(a[mid].first >= b[i] + c[j]) {
r = mid - 1;
} else {
l = mid;
}
}
g.add(i, n + j, 1, -sum[l]);
}
}
cout << -g.flow(s, t).second << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
4 1 2 3 4 1 1 1 1 0 0 1 1 0 1 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 105ms
memory: 26556kb
input:
400 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...
output:
160000
result:
ok single line: '160000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
40 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 10000000000000000...
output:
1600
result:
ok single line: '1600'
Test #4:
score: 0
Accepted
time: 109ms
memory: 26688kb
input:
400 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000...
output:
160000
result:
ok single line: '160000'
Test #5:
score: 0
Accepted
time: 116ms
memory: 27600kb
input:
400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 109ms
memory: 27260kb
input:
400 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 ...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 117ms
memory: 27252kb
input:
400 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
400
result:
ok single line: '400'
Test #8:
score: 0
Accepted
time: 113ms
memory: 27632kb
input:
400 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
10 7 7 7 7 7 7 7 7 7 7 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 0 1 1 1 0 1 0 2
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 148ms
memory: 27304kb
input:
400 13847081798897 874663680339 -1528662074038 10439909774959 1822373103148 -6974433017907 6309247250385 11141586625400 16517676644164 -17331800423448 18505534619011 -19766744660346 6180770287595 10091989087414 568941650316 -16088179604413 4394384705024 -12261134024334 5922925172362 -15877810472552 ...
output:
84539
result:
ok single line: '84539'
Test #12:
score: 0
Accepted
time: 145ms
memory: 27324kb
input:
400 15303324246439 -3723332555981 13456786049020 -5449703381253 14800811164417 14869669832774 -8935406726744 17188618255567 -969955969860 -9782415306754 313401398018 -11039462554654 14986021405358 -14416653774872 8383500342130 -10016955880319 -7595947546269 5157260185522 -1603222670917 -337442035105...
output:
77070
result:
ok single line: '77070'
Test #13:
score: 0
Accepted
time: 153ms
memory: 27452kb
input:
400 -11778519553085 -16255960948010 -6226670878843 13615009183139 14247722110483 -13760764644121 17257861091111 -382049751137 -18229549564421 -4676037861677 16604678606012 13384796753704 4798803674372 -18237959122017 -17890402024503 11526905501044 -5896272864489 15870583446522 -16438263365549 -14109...
output:
88826
result:
ok single line: '88826'
Test #14:
score: 0
Accepted
time: 151ms
memory: 27180kb
input:
400 -5060891419563 11194603021718 7518136467372 10357185701947 3989891421036 8420213756689 2761846713999 -15866137191314 14511434162949 -13547972272308 -11341077208438 1850394936472 6759473618586 -17545628892952 -136933759604 -15416862622640 -1971715904134 -13646627103589 13279907642860 -18895466094...
output:
83447
result:
ok single line: '83447'
Test #15:
score: 0
Accepted
time: 152ms
memory: 26420kb
input:
400 16919086217506 -6384989605958 -13202792652870 -7863676941990 3731048765018 -19255446045143 18393484233509 -4251490219988 15024709618745 -6265764232502 -10565233317818 3772903365601 -9818067060798 -16415763429312 -15128974796983 2275660459409 3297900503632 16182058464702 7219597158423 -7370341301...
output:
86523
result:
ok single line: '86523'
Test #16:
score: 0
Accepted
time: 224ms
memory: 26448kb
input:
400 762 330 158 514 666 258 152 512 342 310 622 476 760 224 92 480 134 98 128 474 578 792 528 274 364 256 424 444 596 418 198 516 404 736 756 664 366 86 794 414 524 748 660 602 200 396 652 398 368 12 332 738 106 34 508 168 136 170 458 620 644 234 482 742 138 236 548 56 772 18 36 522 504 636 150 570 ...
output:
10706600
result:
ok single line: '10706600'
Test #17:
score: 0
Accepted
time: 216ms
memory: 26612kb
input:
400 3739 141 610 1971 120 1939 1421 1820 381 2029 1509 3480 2860 491 1331 2170 3279 1571 2700 371 1170 439 1810 60 3601 2440 2191 1960 3391 3131 2770 2880 1721 779 3809 1379 450 3259 2819 831 820 1619 2669 2280 3250 659 2380 1011 3451 3721 3269 2101 191 2890 2201 2640 669 760 2650 1861 2071 101 3330...
output:
53691575
result:
ok single line: '53691575'
Test #18:
score: 0
Accepted
time: 221ms
memory: 27364kb
input:
400 4137 7519 5259 2062 5059 57 3821 6399 6838 1143 6997 3641 7917 7660 5338 2019 3701 2597 7043 222 3897 4842 3621 4298 4943 6118 2262 4342 439 2920 860 1740 301 7562 3240 1282 7277 1822 4640 2681 2961 759 3501 6359 5579 5901 5000 3799 3577 1778 7600 3399 7458 2721 6143 4718 2280 2518 6761 2480 139...
output:
107404560
result:
ok single line: '107404560'
Test #19:
score: 0
Accepted
time: 220ms
memory: 25996kb
input:
400 6934 1501 9604 148 5275 10294 10862 9693 4225 7765 116 3866 3543 4647 416 11102 2883 2579 8276 1110 2490 4260 8970 7682 8216 10377 6181 11246 10352 6511 4080 269 4737 11309 5489 10829 4947 1649 11580 3065 8102 9715 4619 1560 9056 386 7113 2284 9659 10263 8883 5847 11399 6421 4498 5523 3959 9149 ...
output:
161180629
result:
ok single line: '161180629'
Test #20:
score: 0
Accepted
time: 215ms
memory: 26840kb
input:
400 9044 10507 2803 45 2492 15457 8651 15049 2295 15208 15345 5148 17344 893 19646 11157 4457 7804 16351 2654 18756 7244 18845 4647 1795 11552 9000 450 9743 16905 8508 11707 5703 8255 17255 18456 4604 2448 14155 4347 12849 15899 4995 7199 13199 9704 12994 9442 1104 17796 9501 1354 1892 7892 7652 235...
output:
268564861
result:
ok single line: '268564861'
Test #21:
score: 0
Accepted
time: 205ms
memory: 27316kb
input:
400 134908533454450647 352658606865045145 581684580480093663 497943896187183853 408592795441246050 395165072031649730 146254574430314591 202420064750042310 647642414828915568 601692522952567225 423659429164712656 367352668332523510 16659330113319985 441267266242106592 311084665089366232 308060910038...
output:
404142621
result:
ok single line: '404142621'
Test #22:
score: 0
Accepted
time: 214ms
memory: 26452kb
input:
400 226327251007519290 238750958880838382 425329173403150033 1093881274700431 339265739779043165 418997765106739507 137049815148662314 192757708234547476 135573729210765909 349074451774710340 232391953665474341 266133395498262705 40154598874154329 52014984967455962 331772659893477984 375171531568920...
output:
260934791
result:
ok single line: '260934791'
Test #23:
score: 0
Accepted
time: 199ms
memory: 27632kb
input:
400 269524014049478356 444893904523880884 291696049236349346 247695998750836823 125437811570950709 138324386893112476 632621925085650469 249862747655808151 198789353795262887 197170655685049192 667318156395540426 685887272939973145 479169603920672621 1447043625030237 401490255666325100 3553147393987...
output:
398852089
result:
ok single line: '398852089'
Test #24:
score: 0
Accepted
time: 222ms
memory: 26524kb
input:
400 206684761968587004 540753612188738013 518941982997340809 155408859082188799 509314456610970596 396461325608634748 5808141544800415 516256528119624178 490966425894710583 307806136732640691 174457477712985204 487114098343416438 477055664306066397 27417294768408065 99536586579458612 337033495796696...
output:
284771229
result:
ok single line: '284771229'
Test #25:
score: 0
Accepted
time: 204ms
memory: 27824kb
input:
400 104709922716918275 200659283692875243 234937120796530004 242306130302808787 75683413162551920 92358879309416622 175479935967300382 144320662499313280 141273892653381114 221438699128458677 3631988225540120 293594775120064264 49767688835720269 294632926566924237 126512738496852428 5942375449496023...
output:
411830112
result:
ok single line: '411830112'
Test #26:
score: 0
Accepted
time: 225ms
memory: 27556kb
input:
400 92112158220316422 49665142814083708 18170105895376349 108360361739698886 4365890956761700 5763708133590982 116056757945831490 6983650619010597 50101454843985705 90569351596714450 19272788199756617 65383276276166131 15349493935270706 25467088058513170 36579129693119796 28857137753738956 384163452...
output:
276063785
result:
ok single line: '276063785'
Test #27:
score: 0
Accepted
time: 198ms
memory: 26992kb
input:
400 151693657797317689 247303542798523041 354026862284893685 119534592202446766 251881275437319062 198412375553541731 157413417377042579 213423403126001231 320079167383081959 176752932831743247 335831974200298748 230953010812564270 311900087127196189 263712358349546621 74578477762242816 194984859907...
output:
418813298
result:
ok single line: '418813298'
Test #28:
score: 0
Accepted
time: 228ms
memory: 27092kb
input:
400 128512199698756100 27912001283788196 80181450926331334 143494922359039871 39511499528321639 66736940175768819 155466685031663304 47911518663586299 92163968651847354 162610302706223431 15964993559078544 79562210660835744 95688234307092165 31765430895040143 99986099679113859 124477024770866140 119...
output:
280942132
result:
ok single line: '280942132'
Test #29:
score: 0
Accepted
time: 211ms
memory: 27044kb
input:
400 443014561711115221 316261990970519437 575808081706200325 252418763234976819 298058305788459084 5078827543966376 584636713513502662 448544809608633151 526305296019350622 402558484549552237 163641060879711804 301377251573862491 642358257511892988 421259595404205797 257963572003669108 9956330277516...
output:
421870764
result:
ok single line: '421870764'
Test #30:
score: 0
Accepted
time: 221ms
memory: 27012kb
input:
400 458973924927752908 209187314123266600 544053115329760003 353654080640321655 372978171514507153 144670872849428885 453061166044955211 555746229788300063 174067529767534132 12387989902756644 55988050558053191 272072946746595701 294300685228959522 391206568293033918 535620872917883480 2556141955276...
output:
268798890
result:
ok single line: '268798890'
Test #31:
score: -100
Time Limit Exceeded
input:
400 -8 -8 4 10 -5 -9 5 -4 0 6 -8 3 1 -3 3 4 -1 -4 10 -4 4 -6 1 -2 8 0 -1 -3 -8 5 8 5 -6 -7 -6 -2 -8 -9 -5 -5 -10 4 8 -1 8 0 6 -9 5 -2 -4 3 10 0 5 -1 -1 6 9 -8 -10 -7 -7 -5 10 -6 -1 -3 -7 6 -8 7 7 1 -8 9 0 -9 6 -3 10 -4 -4 3 -9 -2 1 1 -6 -5 10 -9 -9 -3 -10 2 10 -1 -9 -9 4 2 -9 -1 2 -10 -8 -3 -8 3 6 -...