Submission #1074426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074426		anango	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	1 ms	428 KiB

soccer

#include "soccer.h"
using namespace std;
#define int long long
int n;
vector<vector<int>> pref;

int query(int a, int b, int c, int d) {
    return pref[c+1][d+1]-pref[a][d+1]-pref[c+1][b]+pref[a][b];
}

signed biggest_stadium(signed N, vector<vector<signed>> F) {
    //the stadium is valid iff for every pair of cells (a,b) and (c,d), 
    //everything in the paths (a,b) to (a,d) to (c,d) is inside
    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
    n=N;
    pref=vector<vector<int>>(n+1,vector<int>(n+1,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            pref[i+1][j+1] = pref[i+1][j]+pref[i][j+1]-pref[i][j]+F[i][j];
        }
    }
    for (int a=0; a<n; a++) {
        for (int b=0; b<n; b++) {
            for (int c=a; c<n; c++) {
                for (int d=b; d<n; d++) {
                    if (F[a][b]==1 || F[c][d]==1) continue;
                    //everything in the paths (a,b) to (a,d) to (c,d) is inside
                    if (query(a,b,a,d)==0 && query(a,d,c,d)==0) continue;
                    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
                    if (query(a,b,a,c)==0 && query(a,c,c,d)==0) continue;
                    return 888;
                }
            }
        }
    }
    return n*n-pref[n][n];
}

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