QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760030 | #5079. Empty Quadrilaterals | gugugaga# | AC ✓ | 1833ms | 3792kb | C++20 | 13.1kb | 2024-11-18 14:12:26 | 2024-11-18 14:12:32 |
Judging History
answer
/*************************************
* author: marvinthang *
* created: 18.11.2024 11:47:59 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left___
#define right ___right___
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
#include "debug.h"
#else
#define DB(...)
#define db(...) ""
#define debug(...)
#endif
namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } };
template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); }
template <typename T, int D> struct Vec: public vector <Vec<T, D - 1>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename ...Args> Vec(int n = 0, Args ...args): vector <Vec<T, D - 1>>(n, Vec<T, D - 1>(args...)) {} };
template <typename T> struct Vec<T, 1>: public vector<T>{ Vec(int n = 0, const T &val = T()): vector<T>(n, val) {} };
#if __cplusplus < 202002L
template <class T> int ssize(const T &a) { return a.size(); }
#endif
}
struct Point {
long long x, y;
Point(long long x = 0, long long y = 0): x(x), y(y) {}
friend scan_op(Point) { return in >> u.x >> u.y; }
friend print_op(Point) { return out << make_pair(u.x, u.y); }
bool operator == (const Point &other) const { return x == other.x && y == other.y; }
bool operator < (const Point &other) const { return make_pair(x, y) < make_pair(other.x, other.y); }
Point & operator += (const Point &other) {x += other.x; y += other.y; return *this; }
Point & operator -= (const Point &other) { x -= other.x; y -= other.y; return *this; }
Point & operator *= (long long v) { x *= v; y *= v; return *this; }
Point & operator /= (long long v) { x /= v; y /= v; return *this; }
Point operator + (const Point &other) const { return Point(*this) += other; }
Point operator - (const Point &other) const { return Point(*this) -= other; }
Point operator * (long long v) const { return Point(*this) *= v; }
Point operator / (long long v) const { return Point(*this) /= v; }
long long dot(const Point &other) const { return x * other.x + y * other.y; }
long long cross(const Point &other) const { return x * other.y - y * other.x; }
long long norm(void) const { return x * x + y * y; }
double length(void) const { return sqrtl(norm()); }
double angle(const Point &other) const { return acos(dot(other) / length() / other.length()); }
long long cross(const Point &a, const Point &b) const { return (a - *this).cross(b - *this); }
};
int sgn(long long val) { return val < 0 ? -1 : !!val; }
int ccw(const Point &a, const Point &b, const Point &c) { return sgn(a.cross(b, c)); }
double linePointDist(const Point &a, const Point &b, const Point &c, bool isSegment) {
double dist = abs((b - a).cross(c - a)) / (a - b).length();
if (isSegment) {
if ((a - b).dot(c - b) < 0) return (b - c).length();
if ((b - a).dot(c - a) < 0) return (a - c).length();
}
return dist;
}
bool inter1(long long a, long long b, long long c, long long d) {
if (a > b) swap(a, b);
if (c > d) swap(c, d);
return max(a, c) <= min(b, d);
}
bool check_inter(const Point &a, const Point &b, const Point &p) {
return !a.cross(b, p) && inter1(a.x, b.x, p.x, p.x) && inter1(a.y, b.y, p.y, p.y);
}
bool check_inter(const Point &a, const Point &b, const Point &c, const Point &d) {
if (!c.cross(a, d) && !c.cross(b, d))
return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
return ccw(a, b, c) != ccw(a, b, d) && ccw(c, d, a) != ccw(c, d, b);
}
struct Line {
// ax + by = c
long long a, b, c;
Line(long long a = 0, long long b = 0, long long c = 0): a(a), b(b), c(c) {}
Line(const Point &m, const Point &n) {
a = m.y - n.y;
b = n.x - m.x;
c = a * m.x + b * m.y;
}
bool intersect(const Line &other, Point &res) const {
long long x = a * other.b - b * other.a;
if (!x) return false;
res.x = (other.b * c - b * other.c) / x;
res.y = (a * other.c - c * other.a) / x;
return true;
}
bool parallel(const Line &other) const {
return a * other.b - b * other.a == 0;
}
bool equivalent(const Line &other) const {
return a * other.b - b * other.a == 0
&& a * other.c - c * other.a == 0
&& b * other.c - c * other.b == 0;
}
};
void convex_hull(vector <Point> &p) {
if (p.size() <= 1) return;
sort(p.begin(), p.end());
Point p1 = p[0], p2 = p.back();
vector <Point> up {p1}, down {p1};
for (int i = 1; i < (int) p.size(); ++i) {
int c = ccw(p1, p[i], p2);
if (i == (int) p.size() - 1 || c < 0) {
while (up.size() > 1 && ccw(up.end()[-2], up.back(), p[i]) >= 0) up.pop_back();
up.push_back(p[i]);
}
if (i == (int) p.size() - 1 || c > 0) {
while (down.size() > 1 && ccw(down.end()[-2], down.back(), p[i]) <= 0) down.pop_back();
down.push_back(p[i]);
}
}
p = move(up);
p.insert(p.end(), down.rbegin() + 1, down.rend() - 1);
if (p.size() == 2 && p[0] == p[1]) p.pop_back();
}
long long area_x2(const vector <Point> &p) {
long long res = 0;
for (int i = 0; i < (int) p.size(); ++i) res += p[i].cross(p[i == (int) p.size() - 1 ? 0 : i + 1]);
return abs(res);
}
template<
class T, // data type for nodes
T (*op) (const T&, const T&), // operator to combine 2 nodes
T (*e)() // identity element
>
struct SegTree {
SegTree(): SegTree(0) {}
SegTree(int n) : SegTree(vector<T>(n, e())) {}
SegTree(const vector <T>& v) : n(v.size()) {
log = 0;
while ((1 << log) < n) ++log;
size = 1 << log;
d = vector<T>(size << 1, e());
for (int i = 0; i < n; ++i) d[size + i] = v[i];
for (int i = size - 1; i > 0; --i) update(i);
}
// 0 <= p < n
void set(int p, T x) {
assert(0 <= p && p < n);
p += size; d[p] = x;
for (int i = 1; i <= log; ++i) update(p >> i);
}
// 0 <= p < n
T get(int p) const {
assert(0 <= p && p < n);
return d[p + size];
}
// Get product in range [l, r-1]
// 0 <= l <= r <= n
// For empty segment (l == r) -> return e()
T prod(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
T sml = e(), smr = e();
l += size; r += size;
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);
}
T all_prod() const { return d[1]; }
// Binary search on SegTree to find largest r:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false)
template <bool (*f)(T)> int max_right(int l) const { return max_right(l, [](T x) { return f(x); }); }
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= n);
assert(f(e()));
if (l == n) return n;
l += size;
T sm = e();
do {
while (!(l & 1)) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = l << 1;
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return n;
}
// Binary search on SegTree to find smallest l:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false)
template <bool (*f)(T)> int min_left(int r) const { return min_left(r, [](T x) { return f(x); }); }
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= n);
assert(f(e()));
if (r == 0) return 0;
r += size;
T sm = e();
do {
r--;
while (r > 1 && (r & 1)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = r << 1 | 1;
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int n, size, log;
vector <T> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
pair <short, short> op(const pair <short, short> &a, const pair <short, short> &b) {
return pair{max(a.fi, b.fi), min(a.se, b.se)};
}
pair <short, short> e() { return pair{-1, 1000}; }
void process(void) {
short n; cin >> n;
vector <Point> p(n); cin >> p;
long long res = 0;
vector <short> pos_a(n), pos_b(n);
SegTree <pair <short, short>, op, e> st(n);
for (short i = 0; i < n; ++i) {
for (short j = 0; j < i; ++j) {
Point s = p[i], t = p[j];
vector <short> left, right;
for (short k = 0; k < n; ++k) if (k != i && k != j) {
(ccw(s, t, p[k]) > 0 ? left : right).push_back(k);
}
auto solve = [&] (auto &a) {
sort(a.begin(), a.end(), [&] (const short &a, const short &b) {
return ccw(t, p[a], p[b]) > 0;
});
auto b = a;
sort(b.begin(), b.end(), [&] (const short &a, const short &b) {
return ccw(s, p[a], p[b]) > 0;
});
for (short i = 0; i < ssize(b); ++i) {
pos_a[a[i]] = i;
pos_b[b[i]] = i;
}
vector <pair <short, short>> val(ssize(b));
for (short i = 0; i < ssize(b); ++i) {
val[i] = pair{i, pos_a[b[i]]};
}
st = SegTree <pair <short, short>, op, e>(val);
short ta = 0, tb = 0;
for (auto i: a) {
st.set(pos_b[i], e());
auto val = st.prod(0, pos_b[i]);
if (val.fi == -1) ++ta;
else {
if (b[val.fi] == a[val.se]) ++tb;
}
}
return pair{ta, tb};
};
auto [la, lb] = solve(left);
swap(s, t);
auto [ra, rb] = solve(right);
res += (int) la * ra + lb + rb;
}
}
cout << res / 2 << '\n';
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
file("test");
// int t; cin >> t; while (t--)
process();
return (0^0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
5 0 0 2 4 6 2 6 -2 7 3
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
4 0 0 10 0 5 10 3 2
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
10 10 10 1 0 4 8 -1 -4 -7 -4 -3 2 5 -10 -10 -5 1 1 5 -3
output:
170
result:
ok single line: '170'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 0 0 1 0
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 0 0 1 0 10 10
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
4 0 0 1 0 1 1 0 1
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
4 -1000000000 1000000000 1000000000 1000000000 1000000000 -1000000000 -1000000000 -1000000000
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 -8 -3 1 1 7 0 -10 1
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 -5 8 -7 6 8 9 -8 -7 3 1
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
10 -82 -34 9 -90 -67 13 80 -31 -45 51 28 90 -90 -75 58 33 -12 71 90 -80
output:
210
result:
ok single line: '210'
Test #12:
score: 0
Accepted
time: 34ms
memory: 3424kb
input:
100 3759 9658 2910 -9943 4170 9478 -7675 -6575 -6661 7820 6123 8295 9859 -498 9799 42 -2324 -9578 -6860 7649 2269 -9996 8777 4515 8363 5630 6479 8015 -9991 -1944 8574 -7477 8687 -7393 7206 7266 5208 8983 -9081 -4460 -4262 9116 9722 651 9881 -5725 -4899 8911 9867 -592 -7206 7053 -3828 -9346 7471 6976...
output:
3921225
result:
ok single line: '3921225'
Test #13:
score: 0
Accepted
time: 323ms
memory: 3612kb
input:
203 -980345 -265686 -146271 -978033 917841 -441678 -916267 446738 -928177 -428655 850137 -573235 -525140 -879110 -563115 -865718 19693 999740 -304353 -948387 287100 -986973 -329294 -941062 936446 -395687 -933810 -415914 -27770 -989661 120040 -999643 899311 -480711 793647 625727 999790 7708 991740 -1...
output:
68685050
result:
ok single line: '68685050'
Test #14:
score: 0
Accepted
time: 1219ms
memory: 3548kb
input:
300 -109565666 -999084112 987010217 283882659 902175413 602257050 -649185052 919125832 776751215 -617742367 -997974804 287676067 -880568072 -587807228 -537465923 -936971665 -75548128 -997577354 -43885301 997630537 155312299 -972230096 -882508267 -583190585 -562836073 946534352 14128786 994305968 591...
output:
330791175
result:
ok single line: '330791175'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
4 -1 0 0 1 0 0 1 -1
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 -1000000 0 0 1000000 0 0 1000000 -1000000
output:
3
result:
ok single line: '3'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
5 -6 3 4 0 0 0 1 3 0 -1
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 -1 -2 1 0 3 1 5 0 1 4
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
6 0 -4 2 4 8 -1 -2 0 6 -2 5 -3
output:
18
result:
ok single line: '18'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
6 0 -4 2 4 8 -1 -2 0 6 -1 5 -3
output:
19
result:
ok single line: '19'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
6 0 -4 2 4 8 -1 -2 0 1 -1 5 -3
output:
20
result:
ok single line: '20'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
6 0 5 5 5 5 0 1 2 4 3 0 0
output:
22
result:
ok single line: '22'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
7 -63 100 51 -100 100 50 50 92 44 -96 0 90 -100 36
output:
37
result:
ok single line: '37'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
7 -63 100 51 -100 100 50 50 92 44 -96 40 80 -100 36
output:
38
result:
ok single line: '38'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
7 -63 100 51 -100 100 50 50 92 44 -96 0 0 -100 36
output:
39
result:
ok single line: '39'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
7 0 -40 20 40 80 -10 -20 00 60 -20 0 0 50 -30
output:
40
result:
ok single line: '40'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
7 0 -40 20 40 80 -10 -20 00 60 -10 0 0 50 -30
output:
42
result:
ok single line: '42'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
7 0 -40 20 40 80 -10 -20 00 60 -10 20 0 50 -30
output:
42
result:
ok single line: '42'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
7 0 -40 20 40 80 -10 -20 00 10 -10 20 0 50 -30
output:
40
result:
ok single line: '40'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
7 0 -40 20 40 80 -10 -20 00 40 -10 0 0 50 -30
output:
42
result:
ok single line: '42'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
7 -20 30 40 -10 50 30 20 20 40 10 30 0 80 0
output:
42
result:
ok single line: '42'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
9 -1000000 1000000 1000000 1000000 1000000 -1000000 -1000000 -1000000 -1 -2 1 0 3 1 5 0 1 4
output:
113
result:
ok single line: '113'
Test #33:
score: 0
Accepted
time: 1637ms
memory: 3780kb
input:
300 0 -40 20 40 80 -10 -20 00 60 -20 0 0 50 -30 3759 9658 2910 -9943 4170 9478 -7675 -6575 -6661 7820 6123 8295 9859 -498 9799 42 -2324 -9578 -6860 7649 2269 -9996 8777 4515 8363 5630 6479 8015 -9991 -1944 8574 -7477 8687 -7393 7206 7266 5208 8983 -9081 -4460 -4262 9116 9722 651 9881 -5725 -4899 891...
output:
48777998
result:
ok single line: '48777998'
Test #34:
score: 0
Accepted
time: 1645ms
memory: 3520kb
input:
300 -63 100 51 -100 100 50 50 92 44 -96 0 0 -100 36 3759 9658 2910 -9943 4170 9478 -7675 -6575 -6661 7820 6123 8295 9859 -498 9799 42 -2324 -9578 -6860 7649 2269 -9996 8777 4515 8363 5630 6479 8015 -9991 -1944 8574 -7477 8687 -7393 7206 7266 5208 8983 -9081 -4460 -4262 9116 9722 651 9881 -5725 -4899...
output:
45037874
result:
ok single line: '45037874'
Test #35:
score: 0
Accepted
time: 462ms
memory: 3632kb
input:
200 7006 -177 3756 -39 9872 -2618 8860 -8435 8567 -8858 3007 -9855 6431 -78 9573 -1996 645 -7499 3665 -9945 8083 -9316 4098 -11 8951 -1249 5575 -9951 8726 -1037 537 -1720 5520 -9957 9963 -4363 2960 -124 2250 -218 129 -5825 2687 -9786 6657 -9789 4055 -9977 9876 -5238 1496 -746 1577 -8771 2099 -290 12...
output:
9540323
result:
ok single line: '9540323'
Test #36:
score: 0
Accepted
time: 1828ms
memory: 3648kb
input:
300 -501908338 -342208696 -10167056 -346610906 -674262068 -513861820 740719799 -20856381 668020647 118853908 -594640750 -576677796 300321882 646151426 -253013235 593016512 902927188 793410806 -301044865 318724915 -486058015 -496110017 -351177263 -743387574 807088372 54542457 208214529 -524493165 -69...
output:
2795836
result:
ok single line: '2795836'
Test #37:
score: 0
Accepted
time: 1833ms
memory: 3596kb
input:
300 -482422458 -650575249 739358757 -239520925 -788783744 -570062901 -418837911 -745067752 423436230 819110878 841974335 -613836194 -768284217 720559856 -358549450 -256316335 291277639 -897729580 -110268594 -700475931 175686758 -367088054 -530875306 258552250 -212148201 -472842853 503829688 -1360053...
output:
2814628
result:
ok single line: '2814628'
Test #38:
score: 0
Accepted
time: 1830ms
memory: 3660kb
input:
300 356181715 89939368 -72443051 -704507906 -690966591 -279739694 -976538108 -341475796 93551668 -148779235 251274485 -116441701 849551224 -933105925 221551672 -277806162 411595935 -508423498 -490878234 -526198472 901722131 -943273082 -34626519 -349420547 664149659 -282364112 188299626 -41569992 -51...
output:
2708850
result:
ok single line: '2708850'
Test #39:
score: 0
Accepted
time: 1825ms
memory: 3780kb
input:
300 31840392 166106964 358911007 869126535 -621777650 -300184792 -67883155 -75407554 322946753 327310839 278025305 248174787 -126604649 -128856871 726704839 641989969 -321890281 428431976 -4185200 870480695 65151553 948684572 157543013 327022326 -432953230 59313390 130872597 499753387 186866250 7853...
output:
2745119
result:
ok single line: '2745119'
Test #40:
score: 0
Accepted
time: 1829ms
memory: 3656kb
input:
300 -4385121 -503122347 734999363 642635536 515185589 -470338969 375650132 185233124 477179262 101130709 1000000000 1000000000 347997647 -1000000000 -660477475 -261237081 920751336 820224292 524777849 -49304657 580674293 -194540800 748256112 384808467 112178604 145725198 310736009 -631543545 6096309...
output:
2698071
result:
ok single line: '2698071'
Test #41:
score: 0
Accepted
time: 1831ms
memory: 3520kb
input:
300 203045772 308711983 -916118373 318797670 -41260195 -986552053 637476708 950931779 -528765585 -353147471 990296819 98284627 -699115850 782110838 890436583 703447789 -229547159 -709125382 975139869 169993037 509469330 110669354 -675216600 637346207 -953801852 327918372 -22772314 -249145451 9276083...
output:
2796264
result:
ok single line: '2796264'
Test #42:
score: 0
Accepted
time: 1813ms
memory: 3776kb
input:
300 -944766581 480214191 -248842272 -753277593 -448997872 -482488443 -996752701 -260550745 -204818531 281299141 233897455 758175732 688878436 765531134 -823381320 -303603411 403496227 89922133 -357366993 320790475 -1000000000 -59389753 -658015306 826763677 538496279 900395547 703071549 677054086 -45...
output:
3509126
result:
ok single line: '3509126'
Test #43:
score: 0
Accepted
time: 1779ms
memory: 3656kb
input:
300 -182831980 -969196441 414272271 951848039 -548245229 -783948441 801132021 -563171314 -345329194 -598054683 -305508089 -924826054 -218220807 -526211105 -461925755 -713550422 507769882 -860203633 -47508636 999965834 653109611 -727477703 -269444125 -940959595 -230881125 -955536641 569600375 5562516...
output:
4762046
result:
ok single line: '4762046'
Test #44:
score: 0
Accepted
time: 1704ms
memory: 3644kb
input:
300 -771154090 780208833 -885146379 618774890 -929480005 524450406 988987341 -251030240 -528198190 935166148 916434667 495090115 -971988142 -123463555 927578054 473068874 -296540818 995693336 -974419944 401991872 -286359667 -324153147 -434454895 963693999 960637514 -395444073 789192595 -780327590 18...
output:
9910427
result:
ok single line: '9910427'
Test #45:
score: 0
Accepted
time: 1532ms
memory: 3544kb
input:
300 771496631 -715636432 -284370823 -992031886 221646111 -984376736 -502926656 942054170 957030786 250826089 -724998045 856842554 477328838 -923763580 -186630182 990308507 -996566153 -79000362 -997774710 161151873 330239361 976675527 -927892928 -428119195 975961758 153079132 880348453 495048261 6464...
output:
45124100
result:
ok single line: '45124100'
Test #46:
score: 0
Accepted
time: 1414ms
memory: 3636kb
input:
300 -999157963 -18189049 495673938 -900812371 695856806 879843169 -646890746 843856158 -607964011 -861384114 -642823118 846244239 -843220933 678715057 999228694 348303755 -866562377 -584734435 -987109903 -216026832 1000000000 336971228 -758379032 -733372125 -407150315 945513929 969993871 485721162 8...
output:
146429294
result:
ok single line: '146429294'
Test #47:
score: 0
Accepted
time: 1311ms
memory: 3588kb
input:
300 -884798186 738312829 -878931221 747555150 -975559797 -87153305 90984653 986432102 948135107 239847165 -972411704 479962936 -457628206 -898161096 189527452 965324546 685266767 -798324643 702689516 701905705 726151515 -764601703 -951644487 -184972102 770505738 609751583 296791271 934118777 8649066...
output:
262517341
result:
ok single line: '262517341'