답안 #911255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911255	2024-01-18T17:08:49 Z	marvinthang	축구 경기장 (IOI23_soccer)	C++17	65.5 / 100	259 ms	32084 KB

soccer

/*************************************
*    author: marvinthang             *
*    created: 18.01.2024 23:36:31    *
*************************************/

#include "soccer.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

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 << '}'; }
// copied from https://codeforces.com/blog/entry/76149
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) {}
};
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

// end of template

const int INF = 1e9;

int biggest_stadium(int N, vector <vector <int>> F) {
    int cnt = 0;
    REP(i, N) REP(j, N) cnt += F[i][j];
    if (cnt == 1) {
        REP(i, N) REP(j, N) if (F[i][j])
            return N * N - min(i + 1, N - i) * min(j + 1, N - j);
        return N * N;
    }
    if (N <= 30) {
        Vec <int, 4> dp(N, N, N, N + 1, -INF);
        Vec <int, 2> pref(N, N + 1);
        REP(i, N) partial_sum(ALL(F[i]), pref[i].begin() + 1);
        REP(i, N) REP(r, N + 1) REP(l, r) 
            if (pref[i][l] == pref[i][r]) dp[i][i][l][r] = r - l;
        int res = 0;
        REP(x2, N) REPD(x1, x2 + 1) REP(r, N + 1) REP(l, r) if (dp[x1][x2][l][r] >= 0) {
            maximize(res, dp[x1][x2][l][r]);
            FOR(l2, l, r) FORE(r2, l2 + 1, r) {
                if (x1 && pref[x1 - 1][l2] == pref[x1 - 1][r2]) maximize(dp[x1 - 1][x2][l2][r2], dp[x1][x2][l][r] + r2 - l2);
                if (x2 + 1 < N && pref[x2 + 1][l2] == pref[x2 + 1][r2]) maximize(dp[x1][x2 + 1][l2][r2], dp[x1][x2][l][r] + r2 - l2);
            }
        }
        return res;
    }

    vector <int> left(N), right(N);
    REP(x, N) {
        while (left[x] < N && F[x][left[x]]) ++left[x];
        right[x] = left[x];
        while (right[x] < N && !F[x][right[x]]) ++right[x];
        FOR(i, right[x], N) if (!F[x][i]) return 0;
    }
    int l = 0;
    while (left[l] == N) ++l;
    int r = l;
    while (r < N && left[r] < N) ++r;
    FOR(i, r, N) if (left[i] < N) return 0;
    --r;
    int last = -1;
    while (l <= r) {
        int p = -1;
        if (left[l] <= left[r] && right[r] <= right[l]) p = r;
        else if (left[r] <= left[l] && right[l] <= right[r]) p = l;
        if (p == -1) return 0;
        if (last == -1 || (left[p] <= left[last] && right[last] <= right[p])) {
            last = p;
            if (p == l) ++l;
            else --r;
        } else return 0;
    }
    return N * N - cnt;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	1 ms	348 KB	ok
3	Correct	0 ms	348 KB	ok
4	Correct	1 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	1 ms	348 KB	ok
8	Correct	15 ms	2196 KB	ok
9	Correct	230 ms	32084 KB	ok

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	ok
2	Correct	1 ms	348 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	1 ms	348 KB	ok
11	Correct	1 ms	344 KB	ok
12	Correct	0 ms	344 KB	ok
13	Correct	0 ms	344 KB	ok

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	344 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	1 ms	348 KB	ok
5	Correct	0 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	1 ms	348 KB	ok
12	Correct	1 ms	344 KB	ok
13	Correct	0 ms	344 KB	ok
14	Correct	0 ms	344 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	1 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	0 ms	348 KB	ok
19	Correct	1 ms	344 KB	ok
20	Correct	0 ms	428 KB	ok
21	Correct	0 ms	348 KB	ok
22	Correct	1 ms	348 KB	ok
23	Correct	1 ms	344 KB	ok
24	Correct	1 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	0 ms	348 KB	ok

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	344 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	1 ms	348 KB	ok
6	Correct	1 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok
14	Correct	1 ms	344 KB	ok
15	Correct	0 ms	344 KB	ok
16	Correct	0 ms	344 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	1 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	1 ms	344 KB	ok
22	Correct	0 ms	428 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	1 ms	348 KB	ok
25	Correct	1 ms	344 KB	ok
26	Correct	1 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Correct	1 ms	344 KB	ok
30	Correct	5 ms	4956 KB	ok
31	Correct	4 ms	4952 KB	ok
32	Correct	5 ms	5112 KB	ok
33	Correct	4 ms	4956 KB	ok
34	Correct	4 ms	4952 KB	ok
35	Correct	5 ms	4956 KB	ok
36	Correct	4 ms	5060 KB	ok
37	Correct	4 ms	4956 KB	ok
38	Correct	6 ms	4956 KB	ok
39	Correct	4 ms	4956 KB	ok
40	Correct	26 ms	5056 KB	ok
41	Correct	16 ms	4952 KB	ok

Subtask #5
4.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	344 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	1 ms	348 KB	ok
6	Correct	1 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	0 ms	348 KB	ok
9	Correct	0 ms	348 KB	ok
10	Correct	0 ms	348 KB	ok
11	Correct	0 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	1 ms	348 KB	ok
14	Correct	1 ms	344 KB	ok
15	Correct	0 ms	344 KB	ok
16	Correct	0 ms	344 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	1 ms	348 KB	ok
19	Correct	0 ms	348 KB	ok
20	Correct	0 ms	348 KB	ok
21	Correct	1 ms	344 KB	ok
22	Correct	0 ms	428 KB	ok
23	Correct	0 ms	348 KB	ok
24	Correct	1 ms	348 KB	ok
25	Correct	1 ms	344 KB	ok
26	Correct	1 ms	348 KB	ok
27	Correct	0 ms	348 KB	ok
28	Correct	0 ms	348 KB	ok
29	Correct	1 ms	344 KB	ok
30	Correct	5 ms	4956 KB	ok
31	Correct	4 ms	4952 KB	ok
32	Correct	5 ms	5112 KB	ok
33	Correct	4 ms	4956 KB	ok
34	Correct	4 ms	4952 KB	ok
35	Correct	5 ms	4956 KB	ok
36	Correct	4 ms	5060 KB	ok
37	Correct	4 ms	4956 KB	ok
38	Correct	6 ms	4956 KB	ok
39	Correct	4 ms	4956 KB	ok
40	Correct	26 ms	5056 KB	ok
41	Correct	16 ms	4952 KB	ok
42	Partially correct	18 ms	2396 KB	partial
43	Partially correct	15 ms	2392 KB	partial
44	Partially correct	15 ms	2392 KB	partial
45	Partially correct	15 ms	2392 KB	partial
46	Partially correct	15 ms	2396 KB	partial
47	Partially correct	15 ms	2396 KB	partial
48	Correct	15 ms	2396 KB	ok
49	Partially correct	15 ms	2456 KB	partial
50	Partially correct	15 ms	2396 KB	partial
51	Partially correct	15 ms	2396 KB	partial
52	Partially correct	15 ms	2396 KB	partial
53	Partially correct	15 ms	2396 KB	partial
54	Partially correct	15 ms	2392 KB	partial
55	Partially correct	15 ms	2396 KB	partial
56	Partially correct	15 ms	2392 KB	partial
57	Partially correct	15 ms	2396 KB	partial
58	Partially correct	15 ms	2392 KB	partial
59	Partially correct	15 ms	2648 KB	partial

Subtask #6
7.5 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	ok
2	Correct	0 ms	344 KB	ok
3	Correct	1 ms	348 KB	ok
4	Correct	0 ms	348 KB	ok
5	Correct	1 ms	348 KB	ok
6	Correct	0 ms	348 KB	ok
7	Correct	0 ms	348 KB	ok
8	Correct	1 ms	348 KB	ok
9	Correct	15 ms	2196 KB	ok
10	Correct	230 ms	32084 KB	ok
11	Correct	1 ms	348 KB	ok
12	Correct	0 ms	348 KB	ok
13	Correct	0 ms	348 KB	ok
14	Correct	0 ms	348 KB	ok
15	Correct	0 ms	348 KB	ok
16	Correct	0 ms	348 KB	ok
17	Correct	0 ms	348 KB	ok
18	Correct	1 ms	348 KB	ok
19	Correct	1 ms	344 KB	ok
20	Correct	0 ms	344 KB	ok
21	Correct	0 ms	344 KB	ok
22	Correct	0 ms	348 KB	ok
23	Correct	1 ms	348 KB	ok
24	Correct	0 ms	348 KB	ok
25	Correct	0 ms	348 KB	ok
26	Correct	1 ms	344 KB	ok
27	Correct	0 ms	428 KB	ok
28	Correct	0 ms	348 KB	ok
29	Correct	1 ms	348 KB	ok
30	Correct	1 ms	344 KB	ok
31	Correct	1 ms	348 KB	ok
32	Correct	0 ms	348 KB	ok
33	Correct	0 ms	348 KB	ok
34	Correct	1 ms	344 KB	ok
35	Correct	5 ms	4956 KB	ok
36	Correct	4 ms	4952 KB	ok
37	Correct	5 ms	5112 KB	ok
38	Correct	4 ms	4956 KB	ok
39	Correct	4 ms	4952 KB	ok
40	Correct	5 ms	4956 KB	ok
41	Correct	4 ms	5060 KB	ok
42	Correct	4 ms	4956 KB	ok
43	Correct	6 ms	4956 KB	ok
44	Correct	4 ms	4956 KB	ok
45	Correct	26 ms	5056 KB	ok
46	Correct	16 ms	4952 KB	ok
47	Partially correct	18 ms	2396 KB	partial
48	Partially correct	15 ms	2392 KB	partial
49	Partially correct	15 ms	2392 KB	partial
50	Partially correct	15 ms	2392 KB	partial
51	Partially correct	15 ms	2396 KB	partial
52	Partially correct	15 ms	2396 KB	partial
53	Correct	15 ms	2396 KB	ok
54	Partially correct	15 ms	2456 KB	partial
55	Partially correct	15 ms	2396 KB	partial
56	Partially correct	15 ms	2396 KB	partial
57	Partially correct	15 ms	2396 KB	partial
58	Partially correct	15 ms	2396 KB	partial
59	Partially correct	15 ms	2392 KB	partial
60	Partially correct	15 ms	2396 KB	partial
61	Partially correct	15 ms	2392 KB	partial
62	Partially correct	15 ms	2396 KB	partial
63	Partially correct	15 ms	2392 KB	partial
64	Partially correct	15 ms	2648 KB	partial
65	Partially correct	238 ms	31764 KB	partial
66	Partially correct	252 ms	31772 KB	partial
67	Partially correct	232 ms	31768 KB	partial
68	Partially correct	253 ms	31768 KB	partial
69	Partially correct	244 ms	31772 KB	partial
70	Partially correct	229 ms	31828 KB	partial
71	Partially correct	230 ms	31780 KB	partial
72	Partially correct	228 ms	31832 KB	partial
73	Correct	259 ms	31828 KB	ok
74	Correct	234 ms	31792 KB	ok
75	Partially correct	233 ms	31828 KB	partial
76	Partially correct	235 ms	31824 KB	partial
77	Partially correct	232 ms	31764 KB	partial
78	Partially correct	233 ms	31764 KB	partial
79	Partially correct	241 ms	31764 KB	partial
80	Partially correct	239 ms	31820 KB	partial
81	Partially correct	232 ms	31824 KB	partial
82	Partially correct	232 ms	31824 KB	partial
83	Partially correct	236 ms	31780 KB	partial
84	Partially correct	235 ms	31764 KB	partial
85	Partially correct	233 ms	31768 KB	partial
86	Partially correct	248 ms	31768 KB	partial
87	Partially correct	234 ms	31824 KB	partial
88	Partially correct	246 ms	31828 KB	partial
89	Partially correct	232 ms	31768 KB	partial
90	Partially correct	233 ms	31764 KB	partial
91	Partially correct	253 ms	31764 KB	partial
92	Partially correct	244 ms	31768 KB	partial
93	Partially correct	243 ms	31768 KB	partial
94	Partially correct	242 ms	31768 KB	partial
95	Partially correct	234 ms	31828 KB	partial
96	Partially correct	243 ms	31768 KB	partial
97	Partially correct	250 ms	31824 KB	partial
98	Partially correct	230 ms	31768 KB	partial
99	Partially correct	229 ms	31780 KB	partial
100	Partially correct	226 ms	31780 KB	partial
101	Partially correct	234 ms	31768 KB	partial
102	Partially correct	232 ms	31892 KB	partial
103	Partially correct	239 ms	31784 KB	partial
104	Partially correct	232 ms	31824 KB	partial
105	Partially correct	233 ms	31828 KB	partial
106	Partially correct	237 ms	31772 KB	partial
107	Partially correct	228 ms	31764 KB	partial
108	Partially correct	237 ms	31780 KB	partial
109	Partially correct	254 ms	31828 KB	partial

답안 #911255

Compilation message

Subtask #0 0.0 / 0.0

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 22.0 / 22.0

Subtask #4 18.0 / 18.0

Subtask #5 4.0 / 16.0

Subtask #6 7.5 / 30.0

Subtask #0
0.0 / 0.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
22.0 / 22.0

Subtask #4
18.0 / 18.0

Subtask #5
4.0 / 16.0

Subtask #6
7.5 / 30.0