제출 #1240767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240767		noyancanturk	축구 경기장 (IOI23_soccer)	C++17	54 / 100	380 ms	144560 KiB

soccer

#include "soccer.h"

#pragma GCC optimize("O3,unroll-loops")

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

#define pb push_back

using pii=pair<int,int>;

const int lim=2100;

int n;

struct{
  pii tree[2*lim+1];
  pii query(int l,int r){
    // assert(l<=r);
    // cerr<<l<<' '<<r<<'\n';
    int ansmin=INT_MIN;
    int ansmax=INT_MAX;
    for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
      if(l&1){
        ansmin=max(ansmin,tree[l].first);
        ansmax=min(ansmax,tree[l].second);
        l++;
      }
      if(r&1){
        r--;
        ansmin=max(ansmin,tree[r].first);
        ansmax=min(ansmax,tree[r].second);
      }
    }
    return {ansmin,ansmax};
  }
  void update(int p,pii val){
    tree[p+=n]=val;
    for(p>>=1;p;p>>=1){
      tree[p].first=max(tree[p<<1].first,tree[p<<1|1].first);      
      tree[p].second=min(tree[p<<1].second,tree[p<<1|1].second);
    }
  }
}st[lim];

int dp[lim][lim];
pii precalc[lim][lim];
vector<pii>have[lim];

int biggest_stadium(int N,vector<vector<int>>a){
  n=N;
  int haveup[n][n],havedown[n][n];
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      haveup[i][j]=-1;
      havedown[i][j]=n;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(a[i][j]){
        haveup[i][j]=i;
      }else if(i){
        haveup[i][j]=haveup[i-1][j];
      }
    }
  }
  for(int i=n-1;0<=i;i--){
    for(int j=0;j<n;j++){
      if(a[i][j]){
        havedown[i][j]=i;
      }else if(i!=n-1){
        havedown[i][j]=havedown[i+1][j];
      }
    }
  }
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cerr<<haveup[i][j]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cerr<<havedown[i][j]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      st[i].update(j,pii{haveup[i][j],havedown[i][j]});
    }
  }
  int nextind[n][n+1];
  for(int i=0;i<n;i++){
    nextind[i][n]=n;
    for(int j=n-1;0<=j;j--){
      if(j!=n-1){
        nextind[i][j]=nextind[i][j+1];
      }else{
        nextind[i][j]=n;
      }
      if(a[i][j]){
        nextind[i][j]=j;
      }
    }
  }
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cerr<<nextind[i][j]<<' ';
  //   }cerr<<'\n';
  // }cerr<<'\n';
  int ans=0;
  for(int i=0;i<n;i++){
    int gsz=0;
    for(int j=0;j<=n;j++){
      for(auto[x,y]:have[j]){
        dp[x][y]=0;
      }
      have[j].clear();
    }
    // cerr<<"at mid "<<i<<'\n';
    auto insert=[&](pii x,int val) -> void {
      if(!dp[x.first][x.second]){
        have[x.second-x.first].pb(x);
        assert(++gsz<=6000);
      }
      dp[x.first][x.second]=max(dp[x.first][x.second],val);
      // cerr<<"left\n";
    };
    auto trans=[&](pii x,int plim,int past) -> void {
      if(x.second<x.first)return;
      if(!dp[x.first][x.second])precalc[x.first][x.second]=st[i].query(x.first,x.second);
      // cerr<<x.first<<' '<<x.second<<" can go till "<<lims.first<<' '<<lims.second<<'\n';
      insert(x,past+(x.second-x.first+1)*
        (precalc[x.first][x.second].second-precalc[x.first][x.second].first-1-plim));
    };
    int last=-1;
    for(int j=0;j<n;j++){
      if(a[i][j]){
        trans({last+1,j-1},0,0);
        last=j;
      }
    }
    trans({last+1,n-1},0,0);
    for(int sz=n;0<=sz;sz--){
      for(auto[x,y]:have[sz]){
        int val=dp[x][y];
        ans=max(ans,val);
        // cerr<<x<<' '<<y<<" :: "<<val<<'\n';
        pii stuck=precalc[x][y];
        int did=stuck.second-stuck.first-1;
        for(int j:{stuck.first,stuck.second}){
          // cerr<<j<<'\n';
          if(j<0||n<=j)continue;
          last=x-1;
          int p=nextind[j][last+1];
          // cerr<<p<<" is p\n";
          while(p<=y){
            // cerr<<"add "<<last+1<<' '<<p-1<<" because "<<j<<'\n';
            trans({last+1,p-1},did,val);
            last=p;
            p=nextind[j][p+1];
          }
          trans({last+1,y},did,val);
        }
      }
    }
    // cerr<<'\n';
  }
  return ans;
}

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