제출 #1242719

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242719		LeonidCuk	축구 경기장 (IOI23_soccer)	C++17	13.50 / 100	4613 ms	888040 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int n,res=0;
vector<vector<int>>v,pref,pref1;
vector<vector<bool>>g;
void izracuni()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            pref[i][j+1]=pref[i][j]+v[i][j];
            pref1[i+1][j]=pref1[i][j]+v[i][j];
        }
    }
}
int najdi(int l1,int r1,int l2,int r2)
{
    if(r1==r2)return pref1[max(l1,l2)+1][r1]-pref1[min(l1,l2)][r1];
    else return pref[l1][max(r1,r2)+1]-pref[l1][min(r1,r2)];
}
void proveri(int x1,int x2)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(v[i][j]==0)
            {
                if(najdi(x1,x2,x1,j)+najdi(x1,j,i,j)==0||najdi(x1,x2,i,x2)+najdi(i,x2,i,j)==0)
                {
                    g[n*i+j][n*x1+x2]=true;
                    g[n*x1+x2][n*i+j]=true;
                }
            }
        }
    }
}
void lettry(vector<int>v1,vector<int>v2)
{
    if(v1.size()+v2.size()<=res)return;
    if(v2.empty())
    {
        res=max(res,int(v1.size()));return;
    }
    for(int i=0;i<v2.size();i++)
    {
        vector<int>vn1=v1,vn2;
        vn1.push_back(v2[i]);
        for(int j=i+1;j<v2.size();j++)if(g[v2[i]][v2[j]])vn2.push_back(v2[j]);
        lettry(vn1,vn2);
    }
}
int biggest_stadium(int N,vector<vector<int>> G)
{
    n=N;
    v=G;
    pref.resize(n+1,vector<int>(n+1));
    pref1.resize(n+1,vector<int>(n+1));
    g.resize(n*n,vector<bool>(n*n));
    vector<int>temp,temp1;
    izracuni();
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(v[i][j]==0)
            {
                proveri(i,j);
                temp.push_back(n*i+j);
            }
        }
    }
    lettry(temp1,temp);
    return res;
}

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