Submission #988651

#	Time	Username	Problem	Language	Result	Execution time	Memory
988651		Gray	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4558 ms	500 KiB

soccer

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

using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"


// ll n;

vector<vector<bool>> stad;
vector<vector<ll>> reach; 
ll csearch(ll i, vector<vector<int>> &F, ll n){
    if (i==n){
        reach.clear();
        reach.resize(n, vector<ll>(n));
        for (ll j=0; j<n; j++){
            for (ll k=0; k<n; k++){
                reach[j][k]=!stad[j][k];
                if (j) reach[j][k]+=reach[j-1][k];
                if (k) reach[j][k]+=reach[j][k-1];
                if (j and k) reach[j][k]-=reach[j-1][k-1];
            }
        }
        auto calc = [](ll x1, ll y1, ll x2, ll y2){
            return reach[x2][y2]-(x1>0?reach[x1-1][y2]:0)-(y1>0?reach[x2][y1-1]:0)+(x1>0 and y1>0?reach[x1-1][y1-1]:0);
        };
        bool pos=1;
        for (ll j=0; j<n and pos; j++){
            for (ll k=0; k<n and pos; k++){
                if (stad[j][k]){
                    if (F[j][k]) {pos=0; continue;}
                    for (ll x=0; x<n and pos; x++){
                        for (ll y=0; y<n and pos; y++){
                            if (stad[x][y]){
                                if (!((calc(min(x, j), y, max(x, j), y)==0 or calc(min(x, j), k, max(x, j), k)==0)
                                    and (calc(x, min(y, k), x, max(y, k))==0 or calc(j, min(y, k), j, max(y, k))==0))){
                                    // cout << calc(min(x, j), y, max(x, j), y) << " " << calc(min(x, j), k, max(x, j), k) << ln;
                                    // cout << calc(x, min(y, k), x, max(y, k)) << " " << calc(j, min(y, k), j, max(y, k)) << ln;
                                    // cout << j << " " << k << " - " << x << " " << y << ln;
                                    pos=0;
                                }
                            }
                        }
                    }
                }
            }
        }
        // for (ll i=0; i<n; i++){
        //     for (ll j=0; j<n; j++){
        //         cout << stad[i][j] << " ";
        //     }
        //     cout << ln;
        // }
        // cout << pos << ln;
        // cout << ln;
        if (pos){
            // cout << "H\n";
            ll ans=0;
            for (ll i=0; i<n; i++)
                for (ll j=0; j<n; j++)
                    if (stad[i][j]) ans++;
            return ans;
        }else return 0;
    }else{
        ll res=0;
        for (ll j=0; j<(1<<n); j++){
            for (ll k=0; k<n; k++){
                if (j&(1<<k)){
                    stad[i][k]=1;
                }
            }
            res=max(res, csearch(i+1, F, n));
            for (ll k=0; k<n; k++){
                if (j&(1<<k)){
                    stad[i][k]=0;
                }
            }
        }
        return res;
    }
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    stad.clear();
    stad.resize(N, vector<bool>(N));
    return csearch(0, F, N);
}

// int biggest_stadium_F(int N, std::vector<std::vector<int>> F)
// {
//     n=N;
//     vector<vector<ll>> gr(n+1, vector<ll>(n+1));
//     vector<vector<pair<ll, ll>>> A(N+2, vector<pair<ll, ll>>(N+2, {0, n+1}));
//     for (ll i=1; i<=n; i++){
//         for (ll j=1; j<=n; j++){
//             gr[i][j]=F[i-1][j-1];
//             A[i][j].ff=A[i][j-1].ff;
//             if (gr[i][j]){
//                 A[i][j].ff=j;
//             }
//         }
//     }
//     for (ll i=1; i<=n; i++){
//         for (ll j=n; j>=1; j--){
//             A[i][j].ss=A[i][j+1].ss;
//             if (gr[i][j]){
//                 A[i][j].ss=j;
//             }
//         }
//     }
//     // for (ll i=1; i<=n; i++){
//     //     for (ll j=1; j<=n; j++){
//     //         cout << A[i][j].ff << "|" << A[i][j].ss << " ";
//     //     }
//     //     cout << ln;
//     // }
//     // cout << ln;
//     ll res=0;
//     for (ll i=1; i<=n; i++){
//         for (ll j=1; j<=n; j++){
//             // vector<ll> debug;
//             ll l=A[i][j].ff, r=A[i][j].ss;
//             ll ans=-(r-l-1);
//             ll ch=i;
//             while (ch>0 and l<j and r>j and l<r){
                
//                 ans+=r-l-1;
//                 ch--;
//                 l = max(l, A[ch][j].ff);
//                 r = min(r, A[ch][j].ss);
//             }
//             l=A[i][j].ff; r=A[i][j].ss;
//             // debug.push_back(ch);
//             ch = i;
//             while (ch<=n and l<j and r>j and l<r){
//                 ans+=r-l-1;
//                 ch++;
//                 l = max(l, A[ch][j].ff);
//                 r = min(r, A[ch][j].ss);
//             }
//             // debug.push_back(ch);
//             // cout << i << " " << j << " -> " << ans << ": ";
//             // for (auto cch:debug){
//             //     cout << cch << " "; 
//             // }
//             // cout << ln;
//             if (res<ans){
//                 res=ans;
//             }
//         }
//     }
//     return res;
// }

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