QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510260#4942. Robust Defenseideograph_advantageAC ✓3332ms7164kbC++207.1kb2024-08-09 00:48:222024-08-09 00:48:23

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 00:48:23]
  • 评测
  • 测评结果:AC
  • 用时:3332ms
  • 内存:7164kb
  • [2024-08-09 00:48:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb emplace_back
#define ff first
#define ss second
#define SZ(a) int(a.size())

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

using ld = ll;
using pdd = pll;
#define X first
#define Y second

pdd operator+(pdd a, pdd b)
{ return {a.X + b.X, a.Y + b.Y}; }
pdd operator-(pdd a, pdd b)
{ return {a.X - b.X, a.Y - b.Y}; }
pdd operator*(ld i, pdd v)
{ return {i * v.X, i * v.Y}; }
pdd operator*(pdd v, ld i)
{ return {i * v.X, i * v.Y}; }
pdd operator/(pdd v, ld i)
{ return {v.X / i, v.Y / i}; }
ld dot(pdd a, pdd b)
{ return a.X * b.X + a.Y * b.Y; }
ld cross(pdd a, pdd b)
{ return a.X * b.Y - a.Y * b.X; }
ld abs2(pdd v)
{ return v.X * v.X + v.Y * v.Y; };
ld abs(pdd v)
{ return sqrt(abs2(v)); };
int sgn(ld v)
{ return v > 0 ? 1 : (v < 0 ? -1 : 0); }
// int sgn(ld v){ return v > eps ? 1 : ( v < -eps ? -1 : 0); }
int ori(pdd a, pdd b, pdd c)
{ return sgn(cross(b - a, c - a)); }
bool collinearity(pdd a, pdd b, pdd c)
{ return ori(a, b, c) == 0; }
bool btw(pdd p, pdd a, pdd b)
{ return collinearity(p, a, b) && sgn(dot(a - p, b - p)) <= 0; }

bool seg_intersect(pdd p1, pdd p2, pdd p3, pdd p4){
  if(btw(p1, p3, p4) || btw(p2, p3, p4) || btw(p3, p1, p2) || btw(p4, p1, p2))
    return true;
  return ori(p1, p2, p3) * ori(p1, p2, p4) < 0 &&
    ori(p3, p4, p1) * ori(p3, p4, p2) < 0;
}
pdd intersect(pdd p1, pdd p2, pdd p3, pdd p4){
  ld a123 = cross(p2 - p1, p3 - p1);
  ld a124 = cross(p2 - p1, p4 - p1);
  return (p4 * a123 - p3 * a124) / (a123 - a124);
}
pdd perp(pdd p1)
{ return pdd(-p1.Y, p1.X); }
pdd projection(pdd p1, pdd p2, pdd p3)
{ return p1 + (p2 - p1) * dot(p3 - p1, p2 - p1) / abs2(p2 - p1); }
pdd reflection(pdd p1, pdd p2, pdd p3)
{ return p3 + perp(p2 - p1) * cross(p3 - p1, p2 - p1) / abs2(p2 - p1) * 2; }
pdd linearTransformation(pdd p0, pdd p1, pdd q0, pdd q1, pdd r) {
  pdd dp = p1 - p0, dq = q1 - q0, num(cross(dp, dq), dot(dp, dq));
  return q0 + pdd(cross(r - p0, num), dot(r - p0, num)) / abs2(dp);
} // from line p0--p1 to q0--q1, apply to r 

// -1: a // b (if same), 0/1: a < b
int cmp(pll a, pll b, bool same = true, pll dir = pll(1, 0)){
#define is_neg(k) (cross(dir, k) < 0 || (cross(dir, k) == 0 && dot(dir, k) < 0))
  int A = is_neg(a), B = is_neg(b);
  if(A != B)
    return A < B;
  if(sgn(cross(a, b)) == 0)
    return same ? abs2(a) < abs2(b) : -1;
  return sgn(cross(a, b)) > 0;
}

const ll MOD = 998244353;
ll inv(ll a) {
    ll b = MOD - 2;
    ll ans = 1;
    while (b > 0) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int main(){
    StarBurstStream;

    int n, m, S;
    cin >> m >> n >> S;

    S = S * inv(100) % MOD;
    ll D = (1 - S + MOD) % MOD;

    vector<pll> recv(m);
    for (int i = 0; i < m; i++)
        cin >> recv[i].X >> recv[i].Y;
    vector<pll> pts(n);
    for (int i = 0; i < n; i++)
        cin >> pts[i].X >> pts[i].Y;

    vector<ll> spow(n + 1), invspow(n + 1);
    vector<ll> dpow(n + 1), invdpow(n + 1);
    spow[0] = 1; invspow[0] = 1;
    dpow[0] = 1; invdpow[0] = 1;
    for (int i = 1; i <= n; i++) {
        spow[i] = spow[i - 1] * S % MOD, invspow[i] = inv(spow[i]);
        dpow[i] = dpow[i - 1] * D % MOD, invdpow[i] = inv(dpow[i]);
    }

    sort(iter(pts), [&](pll x, pll y) {
        return x.Y != y.Y ? x.Y < y.Y : x.X < y.X;
    });

    vector good(n, vector<bool>(n, true));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (pll p : recv)
                if (ori(pts[i], pts[j], p) < 0
                        || (ori(pts[i], pts[j], p) == 0 && !btw(p, pts[i], pts[j]))) good[i][j] = false;
            
        }
    }

    // all points are distinct
    // cnt[i][j] = # of point k s.t. strictly above ij, and i < k < j
    // cnt2[i][j] = # of points k s.t. strictly in ij
    vector cnt(n, vector<int>(n)), cnt2(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++){
            if (pts[i] >= pts[j]) continue;
            for (int k = 0; k < n; k++) {
                if (pts[i] < pts[k] && pts[k] < pts[j]) {
                    int tmp = ori(pts[i], pts[j], pts[k]);
                    if (tmp > 0) cnt[i][j]++; // only for i < j
                    else if (tmp == 0) cnt2[i][j]++, cnt2[j][i]++;
                }
            }
        }

    debug("cnt");
    for (int i = 0; i < n; i++) pary(iter(cnt[i]));
    debug("cnt2");
    for (int i = 0; i < n; i++) pary(iter(cnt2[i]));

    auto calc_tri = [&](array<int, 3> arr) { // strictly inside
        sort(iter(arr), [&](int x, int y){ return pts[x] < pts[y]; });
        auto [x, y, z] = arr;
        int tmp = ori(pts[x], pts[y], pts[z]);
        if (tmp == 0) return 0;
        else if (tmp < 0) return cnt[x][z] - cnt[x][y] - cnt[y][z] - cnt2[x][y] - cnt2[y][z] - 1;
        else return cnt[x][y] + cnt[y][z] - cnt[x][z] - cnt2[x][z];
    };

    auto getvec = [&](pii x) {
        return pts[x.ss] - pts[x.ff];
    };
    pary(iter(pts));

    ll ans = 0;
    auto solve = [&](int bottom) {
        debug("solve", bottom, pts[bottom]);
        
        pll O = pts[bottom];
        vector<pii> trans;

        for (int j = bottom + 1; j < n; j++) {
            for (int k = bottom + 1; k < n; k++) {
                if (ori(O, pts[j], pts[k]) <= 0) continue;
                if (!good[j][k]) continue;
                trans.pb(pii(j, k));
            }
        }

        sort(iter(trans), [&](pii x, pii y) -> bool{
            int tmp = cmp(getvec(x), getvec(y), false);
            if (tmp != -1) return tmp;
            pll v = getvec(x);
            return dot(v, pts[x.ff]) > dot(v, pts[y.ff]);
        });
        vector<ll> dp(n);
        for (int j = bottom + 1; j < n; j++) {
            if (!good[bottom][j]) continue;
            debug("init trans", j, "cnt", cnt2[bottom][j], "+ 2");
            dp[j] = invdpow[cnt2[bottom][j] + 2] * S % MOD * S % MOD;
        }
        for (auto [i, j] : trans) {
            debug("normal trans", i, j, "cnt", calc_tri({bottom, i, j}), cnt2[i][j], cnt2[bottom][j], "+ 1");
            dp[j] += dp[i] * invdpow[calc_tri({bottom, i, j}) + 1 + cnt2[i][j] + cnt2[bottom][j]] % MOD * S % MOD;
            dp[j] %= MOD;
        }
        for (int j = bottom + 1; j < n; j++) {
            if (!good[j][bottom]) continue;
            debug("end trans", j, dp[j]);
            ans += dp[j];
            ans %= MOD;
        }
    };
    for(int i = 0; i < n; i++) solve(i);

    ans *= dpow[n];
    ans %= MOD;
    cout << ans << "\n";


}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 4 50
0 0
-1 0
3 0
0 1
2 -1

output:

686292993

result:

ok single line: '686292993'

Test #2:

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

input:

3 5 20
3 0
1 3
5 3
0 0
0 6
6 0
6 6
3 3

output:

771443236

result:

ok single line: '771443236'

Test #3:

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

input:

1 2 3
4 5
7 9
-2 -3

output:

184375732

result:

ok single line: '184375732'

Test #4:

score: 0
Accepted
time: 2886ms
memory: 6736kb

input:

500 500 47
7 19
16 17
20 13
1 10
17 9
5 23
12 2
15 12
16 8
11 8
8 12
3 2
11 13
23 0
3 23
13 10
9 12
11 5
8 18
6 0
6 20
3 9
1 21
13 18
5 11
9 15
8 17
6 18
1 8
4 24
7 14
11 11
2 9
8 9
23 3
17 15
21 10
19 7
13 16
0 10
0 7
6 17
11 9
9 4
1 15
21 12
1 24
20 7
21 7
20 0
10 3
3 24
2 12
18 11
20 5
14 20
10 4...

output:

963504722

result:

ok single line: '963504722'

Test #5:

score: 0
Accepted
time: 3126ms
memory: 6744kb

input:

1 500 55
59773527 -48622950
-76633359 443117719
441925049 713512931
-994603144 -68987280
772876381 722131762
511352639 621437284
-136059566 -211230774
-558357374 -936479782
64380588 -111294401
841774806 594567294
515039746 -199627032
-376709851 386524480
-254296132 210052025
-824608562 909197921
118...

output:

185827470

result:

ok single line: '185827470'

Test #6:

score: 0
Accepted
time: 2625ms
memory: 6800kb

input:

1 500 14
20 11
3 8
10 19
3 14
8 14
10 18
19 8
20 10
0 21
11 15
18 10
6 1
1 13
20 8
12 12
13 5
16 13
3 21
4 13
19 17
8 18
21 0
19 3
1 8
3 15
15 0
12 21
5 13
22 6
14 4
21 16
7 4
20 16
17 7
13 2
16 11
9 12
22 16
2 9
21 1
15 12
1 5
20 19
2 4
8 19
17 19
19 19
4 22
8 7
21 18
0 7
13 19
20 2
18 22
10 13
1 1...

output:

682068131

result:

ok single line: '682068131'

Test #7:

score: 0
Accepted
time: 869ms
memory: 5928kb

input:

2 500 46
-403094522 914929192
320656252 -843577464
586600018 642224251
-794800672 841965120
808257851 -869708616
-876762250 -844243852
412194069 -338347112
-173741653 -792568559
399831618 -345749797
910054388 -498157999
-565130894 -50068333
860559597 -840842373
311687063 -961147442
41929748 -5115264...

output:

195721515

result:

ok single line: '195721515'

Test #8:

score: 0
Accepted
time: 930ms
memory: 6120kb

input:

2 500 58
13 22
19 14
13 18
4 9
16 14
16 20
20 3
14 16
8 10
6 7
11 12
12 4
13 21
18 7
15 19
18 19
18 16
1 9
19 5
5 20
10 1
22 11
0 13
10 0
3 17
20 16
4 15
1 5
21 14
12 15
12 10
22 2
10 7
11 22
8 20
3 8
11 14
4 12
9 17
17 6
7 9
6 20
7 13
13 12
20 11
10 16
21 13
19 15
9 3
6 13
18 1
11 10
22 15
11 11
3 ...

output:

46278926

result:

ok single line: '46278926'

Test #9:

score: 0
Accepted
time: 2062ms
memory: 6184kb

input:

3 500 19
477551214 116061473
-309499376 243357246
255365680 -699209646
-750786271 86605756
-807598693 -928286047
330005865 -456468606
-449611339 556234005
686992701 -749656969
-140629011 -481764646
-566102582 679115661
776165074 567358130
899797045 303332290
-546338744 -83179721
-653692787 -26889721...

output:

876479951

result:

ok single line: '876479951'

Test #10:

score: 0
Accepted
time: 1713ms
memory: 6224kb

input:

3 500 55
1 1
18 4
8 15
3 17
22 19
4 5
15 16
6 3
3 19
3 21
3 7
5 6
15 0
2 15
11 14
6 9
10 3
1 18
9 12
0 6
21 20
0 18
21 8
13 11
13 14
2 12
2 5
21 2
0 16
8 5
9 16
2 16
16 11
22 16
18 13
22 13
4 22
1 11
19 17
13 0
3 6
10 18
2 3
8 0
20 9
5 19
6 21
0 19
21 13
14 10
19 5
21 18
0 8
7 17
2 4
22 14
19 9
18 1...

output:

867641008

result:

ok single line: '867641008'

Test #11:

score: 0
Accepted
time: 1044ms
memory: 6124kb

input:

4 500 7
-476636592 -854537496
-908406853 932381623
-707068754 -890003066
58385260 -291357753
-709549006 -724582725
371070418 -158976412
684589595 265105012
-473323100 -691413669
967970807 -711091272
-72050470 197751371
637463713 791283940
-93706748 297610630
-579642099 206973956
33573278 165926209
1...

output:

203258992

result:

ok single line: '203258992'

Test #12:

score: 0
Accepted
time: 1199ms
memory: 5976kb

input:

4 500 14
4 11
10 16
10 19
15 10
14 11
5 17
4 7
12 16
5 2
18 22
13 21
19 0
18 16
5 6
19 17
9 0
13 13
3 10
20 15
14 0
15 11
8 12
22 9
6 7
20 22
15 16
0 11
11 2
20 18
1 18
2 2
1 9
16 12
16 4
5 3
6 20
0 12
14 17
7 17
3 19
4 9
17 0
10 2
19 13
20 11
16 20
13 20
20 13
4 3
12 4
6 12
12 18
6 9
22 20
1 15
3 1...

output:

234632203

result:

ok single line: '234632203'

Test #13:

score: 0
Accepted
time: 1027ms
memory: 5960kb

input:

22 500 85
13 15
13 25
13 16
13 7
13 26
13 20
13 21
13 1
13 3
13 11
13 14
13 18
13 8
13 17
13 9
13 13
13 12
13 6
13 23
13 10
13 19
13 2
24 3
10 15
12 21
18 4
24 26
19 26
22 18
1 25
5 21
25 15
18 16
17 2
12 14
14 11
5 10
27 5
8 22
7 14
11 27
6 0
19 4
17 17
6 6
9 2
3 22
24 21
22 22
3 10
1 26
27 12
2 17...

output:

887019918

result:

ok single line: '887019918'

Test #14:

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

input:

1 3 1
0 0
1 0
2 0
-1 0

output:

976898894

result:

ok single line: '976898894'

Test #15:

score: 0
Accepted
time: 1066ms
memory: 5984kb

input:

5 500 82
5 17
6 17
7 17
8 17
18 17
7 21
8 7
22 8
20 16
19 9
18 20
0 11
10 20
16 4
15 9
11 2
15 20
1 13
20 15
14 16
0 7
21 6
14 12
11 0
16 12
13 11
5 14
17 17
19 21
19 6
22 20
16 1
11 13
7 4
21 8
1 20
14 7
4 20
8 10
16 14
10 7
7 6
21 3
0 14
19 19
1 9
8 1
19 5
6 18
15 16
8 2
11 7
16 8
0 1
15 8
0 13
15...

output:

725728375

result:

ok single line: '725728375'

Test #16:

score: 0
Accepted
time: 1167ms
memory: 6188kb

input:

7 500 56
33 39
24 12
22 6
30 30
29 27
21 3
23 9
2 22
30 2
0 35
33 37
26 14
32 33
42 40
0 23
30 18
20 38
36 37
38 36
23 39
3 6
6 13
38 14
28 20
23 31
38 21
6 31
1 7
40 37
21 0
26 12
22 21
16 17
32 34
13 4
11 28
37 33
33 28
1 11
16 1
2 34
4 9
15 24
23 7
20 3
14 38
11 7
40 41
29 33
34 15
1 24
38 41
23 ...

output:

312153189

result:

ok single line: '312153189'

Test #17:

score: 0
Accepted
time: 693ms
memory: 5852kb

input:

500 500 53
839260745 344916325
839260745 235500481
839260745 671386212
839260745 -280235618
839260745 -86590303
839260745 337510956
839260745 -182522139
839260745 -597396479
839260745 822607915
839260745 660094661
839260745 926197409
839260745 -533044257
839260745 235274122
839260745 -168053127
8392...

output:

792585131

result:

ok single line: '792585131'

Test #18:

score: 0
Accepted
time: 1027ms
memory: 5940kb

input:

125 500 64
-141451513 335567220
-569848697 335567220
-388992260 335567220
-992701005 335567220
-250590710 335567220
-91355773 335567220
-489615703 335567220
7554245 335567220
-226231803 335567220
-839346275 335567220
-902123132 335567220
-588045845 335567220
-383826078 335567220
-575357505 335567220...

output:

270132479

result:

ok single line: '270132479'

Test #19:

score: 0
Accepted
time: 546ms
memory: 5224kb

input:

500 500 42
-79195047 -961485472
335635421 -865755364
466131514 -835640881
42257505 -933457960
362168850 -859632265
545938293 -817223932
383691468 -854665507
988199242 -715163713
351944051 -861991834
122048840 -915044575
39515259 -934090786
201812966 -896637469
-139851292 -975483067
-160417656 -98022...

output:

277408113

result:

ok single line: '277408113'

Test #20:

score: 0
Accepted
time: 512ms
memory: 5784kb

input:

500 500 92
596423239 295663345
126269009 295663345
392209845 295663345
946086763 295663345
-587440099 295663345
609944971 295663345
541149279 295663345
76239547 295663345
355877801 295663345
-909476583 295663345
-684641161 295663345
911167557 295663345
-751247183 295663345
386126075 295663345
-97494...

output:

342415679

result:

ok single line: '342415679'

Test #21:

score: 0
Accepted
time: 1911ms
memory: 6220kb

input:

23 500 19
-168796364 -738629922
840538535 -391018528
-851903656 -973889674
749805159 -422266784
-480772972 -846073570
297233476 -578130882
132006547 -635034456
635226052 -461727426
-817314244 -961977202
199283894 -611864374
-381419119 -811856452
-377811016 -810613834
611534858 -469886590
-64692178 -...

output:

867381472

result:

ok single line: '867381472'

Test #22:

score: 0
Accepted
time: 1543ms
memory: 6160kb

input:

4 500 5
446114147 62330869
381448696 114714436
834106853 -251970533
122786892 324248704
187279696 124044421
578890722 807472082
-71209461 481399405
467965318 110897752
262440310 189995290
-538945687 508863404
-617030073 -275412300
-197870727 117814473
439229417 74931589
242643495 717650048
30809842 ...

output:

105841299

result:

ok single line: '105841299'

Test #23:

score: 0
Accepted
time: 3332ms
memory: 7072kb

input:

500 500 18
527 1274
-1072 -960
-1065 -967
1421 58
857 1118
1378 -412
-1292 -631
1080 -1013
-815 -1156
357 -1344
-652 1272
1177 -898
1125 -966
1412 -238
198 1353
-216 1375
-1388 375
-954 1107
582 1255
-717 -1209
-399 -1324
-516 1318
-1383 -340
213 -1367
377 -1340
-1413 227
-1149 931
1014 987
-530 131...

output:

826686575

result:

ok single line: '826686575'

Test #24:

score: 0
Accepted
time: 2471ms
memory: 6416kb

input:

500 500 61
1348 -1383
1765 567
-1308 1378
-1122 -1626
-1040 1605
-1486 1166
-545 -1865
1810 368
1114 1675
1786 481
-1010 -1687
-623 1796
1847 130
-1858 -63
-1856 -33
711 -1777
956 -1670
1830 263
-1326 -1476
1840 -276
-1520 1116
1733 -712
508 -1837
1481 1287
1806 -469
-1385 1294
-1718 -848
-724 -1810...

output:

101380411

result:

ok single line: '101380411'

Test #25:

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

input:

1 3 99
0 0
0 1
0 -1
0 2

output:

987945467

result:

ok single line: '987945467'

Test #26:

score: 0
Accepted
time: 3213ms
memory: 7164kb

input:

1 500 84
0 0
-528626526 850274457
231477980 980386745
-928052116 -435062741
120978206 -985648195
450564112 -899544475
-136854600 984213577
816504922 624013015
979145282 -145180217
-762063278 -750298027
-650606796 764170737
-470267338 880410759
-251659560 961730939
902130288 445108619
262092636 97512...

output:

830242511

result:

ok single line: '830242511'

Test #27:

score: 0
Accepted
time: 3200ms
memory: 6816kb

input:

500 500 32
132 1739
1215 1218
-1102 1519
1620 683
1110 -1433
638 -1684
-1751 311
-884 1625
-1154 1486
1157 -1390
1386 1056
-65 -1752
1255 -1292
1766 84
-268 -1724
-816 -1572
1517 -917
401 1676
587 -1698
1669 -534
-1596 -772
-1619 -712
662 1570
1274 1170
-1741 -214
1692 482
365 -1741
617 -1690
-474 -...

output:

696038389

result:

ok single line: '696038389'

Test #28:

score: 0
Accepted
time: 495ms
memory: 5116kb

input:

500 500 65
432253349 -481926159
-376816475 112183262
781308082 936712612
247234697 -757378669
501254368 -910074338
-99238771 435023770
700216182 446258009
-313205674 312197967
481562691 -672726561
788848861 -896921357
259254316 513368703
-4675860 -322240377
-307547478 988464243
-375031315 100008950
...

output:

826440261

result:

ok single line: '826440261'

Test #29:

score: 0
Accepted
time: 458ms
memory: 5108kb

input:

451 500 16
396671259 -386006440
668340741 827795851
-6858858 -599240263
208373337 502052889
-254230496 -594403716
-837643412 -239991778
740834719 -674070836
-279976628 250975793
-11467466 -917838738
-122208252 -432480867
564533642 85955733
332571090 763072513
177473146 -425386399
-395577764 -3887236...

output:

294803840

result:

ok single line: '294803840'

Test #30:

score: 0
Accepted
time: 2701ms
memory: 6800kb

input:

3 500 97
328578360 500000001
264781007 500000000
328578359 500000001
989966597 875321135
630239494 543805882
994085850 804466456
500000000 1000000000
7343998 471796011
944228688 383988188
290214042 443683005
10983492 531385492
616623513 546601837
501996981 390131306
740558923 802436874
752293819 813...

output:

586259231

result:

ok single line: '586259231'

Test #31:

score: 0
Accepted
time: 2649ms
memory: 6988kb

input:

3 500 33
587599306 499999999
471788361 500000000
587599305 499999999
210313053 314632869
647883985 1580333
617255658 301702573
735308426 471987789
315987477 579447631
593610495 385548804
682729682 549093584
353748846 805657954
658513175 151847362
362633781 910695628
937199763 672717111
985460116 421...

output:

10201997

result:

ok single line: '10201997'

Test #32:

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

input:

500 2 2
-692151163 -692151163
-454664468 -454664468
-144826769 -144826769
214233013 214233013
135793196 135793196
-156501079 -156501079
-414475065 -414475065
-651049086 -651049086
700216564 700216564
170127714 170127714
587556453 587556453
806334675 806334675
856030266 856030266
228901602 228901602
...

output:

192860809

result:

ok single line: '192860809'

Test #33:

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

input:

500 3 98
-512340885 -512340885
-997029267 -997029267
-690147962 -690147962
451031393 451031393
660079977 660079977
-682847635 -682847635
-770210362 -770210362
-670642835 -670642835
-199677781 -199677781
812980776 812980776
30263600 30263600
79584620 79584620
533146990 533146990
723768241 723768241
8...

output:

871666970

result:

ok single line: '871666970'

Test #34:

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

input:

500 4 69
-147393506 -147393506
797423132 797423132
-651139712 1000000000
-525783468 1000000000
-1000000000 -523636520
588348702 1000000000
996032759 1000000000
708229878 1000000000
-839163871 1000000000
-1000000000 498930317
383458738 383458738
-270192638 1000000000
-1000000000 19807507
768110798 10...

output:

975631124

result:

ok single line: '975631124'

Test #35:

score: 0
Accepted
time: 491ms
memory: 5236kb

input:

500 500 81
206580046 134047298
-427778766 466093599
-22036603 -379577430
-424239741 254556669
784782806 224166348
884671106 -983006421
-351956966 -336961309
-354193877 -749463345
-324116521 -448498195
-213324401 495343715
-902406237 482217448
-335066351 676938165
-545768594 -621327963
269635892 -965...

output:

365281330

result:

ok single line: '365281330'

Test #36:

score: 0
Accepted
time: 504ms
memory: 5236kb

input:

500 500 68
30 7
14 22
25 12
31 22
5 13
14 17
17 2
10 13
2 30
19 6
3 20
5 12
14 15
11 20
5 25
18 2
26 27
23 17
20 3
15 23
6 20
16 3
14 6
16 1
30 25
23 7
17 17
15 19
19 24
14 14
13 22
15 2
25 23
18 13
17 18
30 19
11 9
12 17
3 31
22 4
18 20
22 8
22 28
14 26
31 17
15 11
7 4
24 18
24 16
26 13
30 30
28 8
...

output:

214004082

result:

ok single line: '214004082'

Test #37:

score: 0
Accepted
time: 1862ms
memory: 6252kb

input:

500 500 2
430129881 238289397
-914438860 479901040
-408661489 441351738
-780641660 -339519020
-484668146 667719151
-407348873 -402482170
-647219856 148970953
327834986 138603178
-130700654 -147204101
-484955130 802278630
-131282996 841226167
223799381 -384703697
-434819306 829705576
-597846325 -1690...

output:

48153586

result:

ok single line: '48153586'