제출 #1074442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074442		anango	축구 경기장 (IOI23_soccer)	C++17	0 / 100	4546 ms	4696 KiB

soccer

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

int INF = 1LL<<30;

int query(int a, int b, int c, int d) {
    if (a<c) swap(a,c);
    if (b<d) swap(b,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=0; c<n; c++) {
                for (int d=0; 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 INF;
                }
            }
        }
    }
    //cout << "jambloat " << pref[n][n] << endl;
    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