제출 #1240588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240588		noyancanturk	Soccer Stadium (IOI23_soccer)	C++17	0 / 100	0 ms	328 KiB

soccer

#include "soccer.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

using pii=pair<int,int>;

int biggest_stadium(int n,vector<vector<int>>A){
  int a[n][n+2];
  for(int i=0;i<n;i++){
    a[i][0]=a[i][n+1]=1;
    for(int j=0;j<n;j++){
      a[i][j+1]=A[i][j];
    }
  }
  vector<pii>v[n];
  for(int i=0;i<n;i++){
    int last=0;
    for(int j=1;j<n+2;j++){
      if(a[i][j]==1){
        v[i].pb({last+1,j-1});
        last=j;
      }
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
    vector<pair<pii,int>>dp;
    for(pii x:v[i]){
      dp.pb({x,x.second-x.first+1});
      ans=max(ans,dp.back().second);
    }
    for(int j=1;j<n;j++){
      if(i-j<0||n<=i+j){
        break;
      }
      vector<pair<pii,int>>newdp;
      int midind=0,ind1=0,ind2=0;
      while(1){
        auto[x1,y1]=v[i-j][ind1];
        auto[x2,y2]=v[i+j][ind2];
        int intx=max(x1,x2),inty=min(y1,y2);
        while(midind<dp.size()&&dp[midind].first.second<intx){
          midind++;
        }
        for(int gy:{midind,midind+1}){
          if(dp.size()<=gy)continue;
          auto[x,y]=dp[gy].first;
          int cost=dp[gy].second;
          int X1=max(x1,x),Y1=min(y1,y);
          int X2=max(x2,x),Y2=min(y2,y);
          if(Y1<X1||Y2<X2)continue;
          int intX=max(X1,X2),intY=min(Y1,Y2);
          if(intY<intX)continue;
          newdp.pb({pii{intX,intY},cost+intY-intX+1+max(Y1-X1+1,Y2-X2+1)});
          ans=max(ans,newdp.back().second);
        }
        if(ind1+1==v[i-j].size()&&ind2+1==v[i+j].size()){
          break;
        }else if(ind1+1==v[i-j].size()){
          ind2++;
        }else if(ind2+1==v[i+j].size()){
          ind1++;
        }else if(v[i-j][ind1+1].first<v[i+j][ind2+1].first){
          ind1++;
        }else{
          ind2++;
        }
      }
      dp=newdp;
    }
  }
  return ans;
}

• 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