제출 #840704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
840704		PurpleCrayon	축구 경기장 (IOI23_soccer)	C++17	70 / 100	4582 ms	1027788 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10;
 
struct Sparse {
    vector<vector<int>> sparse;
    Sparse() {}
    Sparse(vector<int>& v) {
        int n = v.size();
        sparse.push_back(v);
        for (int i = 1; (1 << i) <= n; i++) {
            sparse.push_back(vector<int>(n - (1 << i) + 1));
            for (int j = 0; j + (1 << i) <= n; j++) {
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
            }
        }
    }
 
    int qry(int l, int r) {
        assert(l <= r);
        int b = 31 - __builtin_clz(r - l + 1);
        // cerr << "> " << l << ' ' << r << ''
        return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
    }
} ones[M], twos[M];
 
int check_full(int N, std::vector<std::vector<int>> F) {
    vector<int> one, two;
    vector<pair<int, int>> ranges;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int mn = N, mx = -1, cnt = 0;
        for (int j = 0; j < N; j++) {
            if (!F[i][j]) {
                mn = min(mn, j);
                mx = max(mx, j);
                cnt++;
                ans++;
            }
        }
 
        if (cnt && cnt != mx - mn + 1) return 0;
        one.push_back(mn);
        two.push_back(mx);
        if (cnt) ranges.push_back({mn, mx});
    }
 
    auto contains = [&](pair<int, int> p1, pair<int, int> p2) {
        return p1.first <= p2.first && p2.second <= p1.second;
    };
 
    for (auto p1 : ranges) {
        for (auto p2 : ranges) {
            if (!contains(p1, p2) && !contains(p2, p1))
                return 0;
        }
    }
 
    int m1 = min_element(one.begin(), one.end()) - one.begin();
    for (int i = m1; i > 0; i--) if (one[i] > one[i-1]) return 0;
    for (int i = m1; i < N-1; i++) if (one[i] > one[i+1]) return 0;
    int m2 = max_element(two.begin(), two.end()) - two.begin();
    for (int i = m2; i > 0; i--) if (two[i] < two[i-1]) return 0;
    for (int i = m2; i < N-1; i++) if (two[i] < two[i+1]) return 0;
    return ans;
}
 
int run_subtask(int N, std::vector<std::vector<int>> F) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (F[i][j]) {
                return N * N - min(i + 1, N - i) * min(j + 1, N - j);
            }
        }
    }
    assert(false);
}
 
int get_cost(int i, int l, int r) {
    // int one = i + 1, two = N - i;
    // for (int i = l; i <= r; i++) one = min(one, up[i]);
    // for (int i = l; i <= r; i++) two = min(two, down[i]);
    // return max(0, one + two - 1);
    // cerr << l << ' ' << r << endl;
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}
 
vector<int> impl[M][M];
vector<int> impr[M][M];
vector<int> has[M][M];
unordered_map<ll, int> dp;
 
ll h(int a, int b, int c) {
    return (long long) a * M * M + b * M + c;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    int test = check_full(N, F);
    if (test) return test;
 
    int cnt_fill = 0;
    for (auto v : F) for (auto x : v) cnt_fill += x;
    if (cnt_fill == 1) {
        return run_subtask(N, F);
    }
 
     for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            while (i - up[j] >= 0 && !F[i - up[j]][j]) up[j]++;
            while (i + down[j] < N && !F[i + down[j]][j]) down[j]++;
            // if (i == 0) cerr << up[j] << ' ' << down[j] << endl;
            // if (i == 0) cerr << "> " << F[i][i + 1]
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
        // vector<vector<int>> dp(N, vector<int>(N, -INF));
        // for (int l = 0; l < N; l++) {
        //     for (int r = N-1; r >= l; r--) {
        //         dp[l][r] = get_cost(l, r) * (r - l + 1);
        //     }
        // }
 
        // for (int l = 0; l < N; l++) {
        //     for (int r = N-1; r > l; r--) if (dp[l][r] >= 0) {
        //         // if (i == 2) cerr << l << ' ' << r << ' ' << dp[l][r] << endl;
        //         // if (i == 2 && l == 0 && r == 4) cerr << ">> " << get_cost(l + 1, r) << ' ' << get_cost(l, r) << endl;
        //         dp[l+1][r] = max(dp[l+1][r], (get_cost(l + 1, r) - get_cost(l, r)) * (r - l) + dp[l][r]);
        //         dp[l][r-1] = max(dp[l][r-1], (get_cost(l, r - 1) - get_cost(l, r)) * (r - l) + dp[l][r]);
        //     }
        // }
 
        // for (int i = 0; i < N; i++)
        //     for (int j = 0; j < N; j++) {
        //         ans = max(ans, dp[i][j]);
        //     }
    }
 
    auto add_imp = [&](int i, int l, int r) {
        has[l][r].push_back(i);
        impl[i][l].push_back(r);
        impr[i][r].push_back(l);
    };
 
    for (int i = 0; i < N; i++) {
        vector<int> blocks{-1};
        for (int j = 0; j < N; j++) if (F[i][j])
            blocks.push_back(j);
        
        blocks.push_back(N);
 
        for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
            int l = blocks[j-1]+1, r = blocks[j]-1;
            for (int k = l; k <= r; k++) {
                add_imp(i, k, r);
                if (k != r) add_imp(i, l, k);
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sort(impl[i][j].begin(), impl[i][j].end());
            sort(impr[i][j].begin(), impr[i][j].end());
        }
    }
 
    auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
        if (ni < 0 || ni >= N) return;
        int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), l) - impr[ni][r].begin();
        if (nl < sz(impr[ni][r])) {
            nl = impr[ni][r][nl];
            dp[h(ni, nl, r)] = max(dp[h(ni, nl, r)], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
        }
 
        int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), r) - impl[ni][l].begin() - 1;
        if (nr >= 0) {
            nr = impl[ni][l][nr];
            dp[h(ni, l, nr)] = max(dp[h(ni, l, nr)], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    // cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    for (int l = 0; l < N; l++) {
        for (int r = N-1; r >= 0; r--) {
            for (int i : has[l][r]) {
                int cur_cost = get_cost(i, l, r);
                dp[h(i, l, r)] = max(dp[h(i, l, r)], cur_cost * (r - l + 1));
                // cerr << l << ' ' << r << ' ' << i << ' ' << dp[{i, l, r}] << endl;
 
                int top = i - ones[i].qry(l, r);
                int bot = i + twos[i].qry(l, r);
                upd(i, l, r, dp[h(i, l, r)], cur_cost);
                upd(top, l, r, dp[h(i, l, r)], cur_cost);
                upd(bot, l, r, dp[h(i, l, r)], cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& [_, v] : dp) ans = max(ans, v);
    // cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30