Submission #843062

#	Time	Username	Problem	Language	Result	Execution time	Memory
843062		nonono	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	1660 ms	314288 KiB

soccer

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

const int mxN = 2000;

map<int, int> dp[mxN][mxN];

int full(int N, vector<vector<int>> F) {
    vector<vector<int>> sum(N, vector<int> (N, 0));
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            sum[i][j] = F[i][j];
            
            if(i) sum[i][j] += sum[i - 1][j];
            if(j) sum[i][j] += sum[i][j - 1];
            if(i && j) sum[i][j] -= sum[i - 1][j - 1]; 
            
        }
    }
    
    auto Area = [&] (int x, int y, int u, int v) {
        return sum[u][v] - (x ? sum[x - 1][v] : 0) - (y ? sum[u][y - 1] : 0) + (x && y ? sum[x - 1][y - 1] : 0);
    };
    
    auto Range = [&] (int x, int L, int R) {
        int low = x, high = x - 1;
        for(int i = 10; i >= 0; i --) {
            if(low - (1 << i) >= 0 && Area(low - (1 << i), L, x, R) == 0) low -= (1 << i);
            if(high + (1 << i) < N && Area(x, L, high + (1 << i), R) == 0) high += (1 << i);
        }
        
        return make_pair(low, high);
    };   
    
    function<int(int, int, int)> DP = [&] (int x, int L, int R) {
        if(dp[L][R].count(x)) return dp[L][R][x];
        auto [low, high] = Range(x, L, R);
        if(x != low) return DP(low, L, R);
        
        int ans = 0;
        for(int i = L; i <= R; i ++) {
            auto check = [&] (int r) {
                return low - 1 >= 0 && Area(low - 1, i, low - 1, r) == 0;
            };
            
            if(check(i) == 0) continue ;
            
            int j = i;
            for(int k = 10; k >= 0; k --) if(j + (1 << k) <= R && check(j + (1 << k))) j += (1 << k);
            auto [_low, _high] = Range(low - 1, i, j);
            ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
            i = j;
        }
        
        for(int i = L; i <= R; i ++) {
            auto check = [&] (int r) {
                return high + 1 < N && Area(high + 1, i, high + 1, r) == 0;
            };
            
            if(check(i) == 0) continue ;
            
            int j = i;
            for(int k = 10; k >= 0; k --) if(j + (1 << k) <= R && check(j + (1 << k))) j += (1 << k);
            auto [_low, _high] = Range(high + 1, i, j);
            ans = max(ans, DP(_low, i, j) + (low - _low + _high - high) * (j - i + 1));
            i = j;
        }
        
        return dp[L][R][x] = ans;
    };
    
    int result = 0;
    for(int i = 0; i < N; i ++) {
        pair<int, int> x = Range(i, 0, N - 1);
        result = max(result, DP(i, 0, N - 1) + (x.second - x.first + 1) * N);
    }
    
    return result;
}
 
int biggest_stadium(int N, vector<vector<int>> F) {
    return full(N, F);
}

• 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: 30 / 30