제출 #1241850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241850		candi_ositos	축구 경기장 (IOI23_soccer)	C++20	29.50 / 100	2947 ms	197556 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
int test(int N, vector <vector <int> > F){
    int lmt=-1, rmt=-1, umt=-1, dmt=-1;
    vector <int> ums, dms, rms, lms;
    ums.assign(N, -1);
    dms.assign(N, -1);
    rms.assign(N, -1);
    lms.assign(N, -1);
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(F[i][j]){
                if(i>0){
                    if(!F[i-1][j] && umt==-1){
                        umt=i;
                    }
                }
                if(j>0){
                    if(!F[i][j-1] && (lmt==-1 || lmt>j)){
                        lmt=j;
                    }
                }
                if(i<N-1){
                    if(!F[i+1][j]){
                        dmt=i;
                    }
                }
                if(j<N-1){
                    if(!F[i][j+1] && rmt<j){
                        rmt=j;
                    }
                }
            }
            else{
                if(ums[j]==-1){
                    ums[j]=i;
                }
                if(lms[i]==-1){
                    lms[i]=j;
                }
                rms[i]=j;
                dms[j]=i;
            }
        }
    }
    if((umt<=dmt+1 && (umt!=-1 && dmt!=-1)) || (lmt<=rmt+1 && (lmt!=-1 && rmt!=-1))){
        return 0;
    }
    for(int i=0; i<N; ++i){
        if(ums[i]!=-1){
            for(int j=0; j<N; ++j){
                if(dms[j]!=-1){
                    if(F[ums[i]][j] && F[dms[j]][i]){
                        return 0;
                    }
                }
            }
        }
    }
    for(int i=0; i<N; ++i){
        if(lms[i]!=-1){
            for(int j=0; j<N; ++j){
                if(rms[j]!=-1){
                    if(F[j][lms[i]] && F[i][rms[j]]){
                        return 0;
                    }
                }
            }
        }
    }
    vector <bool> bsc;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(!F[i][j]){
                bsc.push_back(0);
            }
        }
    }
    int aux=bsc.size();
    if(aux==0){
        aux=-1;
    }
    return aux;
}
int biggest_stadium(int N, vector <vector <int> > F)
{
    int nosirvo=test(N, F);
    if(nosirvo>0){
        return nosirvo;
    }
    int tc=0;
    int x=-1;
    int y=-1;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(F[i][j]){
                ++tc;
                x=i;
                y=j;
            }
        }
    }
    if(tc==0){
        return N*N;
    }
    if(tc==1){
        if(x>N-x-1){
            x=N-x-1;
        }
        if(y>N-y-1){
            y=N-y-1;
        }
        return N*N-(x+1)*(y+1);
    }
    if(tc==N*N-1){
        return 1;
    }
    if(N>7){
        return 0;
    }
    vector <vector <vector <int> > > TQ;
    TQ.assign(1, vector <vector <int> >(N, vector <int>(N, 1)));
    if(!F[0][0]){
        TQ.push_back(TQ[0]);
        TQ[1][0][0]=1;
    }
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(j>0 || i>0){
                int k=TQ.size();
                if(!F[i][j]){
                    for(int l=0; l<k; ++l){
                        TQ.push_back(TQ[l]);
                        TQ[TQ.size()-1][i][j]=0;
                        vector <vector <int> > aux=TQ[TQ.size()-1];
                        for(int m=j+1; m<N; ++m){
                            aux[i][m]=F[i][j];
                        }
                        int aguss=test(N, aux);
                        if(aguss==0){
                            TQ.pop_back();
                        }
                    }
                }
            }
        }
    }
    int mx=0;
    for(unsigned int i=0; i<TQ.size(); ++i){
        int aux;
        aux=test(N, TQ[i]);
        if(aux>mx){
            mx=aux;
        }
    }
    return mx;
}

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