Submission #1240722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240722		noyancanturk	Soccer Stadium (IOI23_soccer)	C++17	70 / 100	4598 ms	145280 KiB

soccer

#include "soccer.h"

#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];

map<pii,int>dp[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]});
    }
  }
  vector<int>inds[n];
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(a[i][j]){
        inds[i].pb(j);
      }
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<=n;j++){
      dp[j].clear();
    }
    // cerr<<"at mid "<<i<<'\n';
    auto insert=[&](pii x,int val) -> void {
      dp[x.second-x.first][x]=max(dp[x.second-x.first][x],val);
      // cerr<<"left\n";
    };
    auto trans=[&](pii x,int plim,int past) -> void {
      if(x.second<x.first)return;
      pii lims=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)*
        (lims.second-lims.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[rang,val]:dp[sz]){
        auto[x,y]=rang;
        // cerr<<x<<' '<<y<<" :: "<<val<<'\n';
        ans=max(ans,val);
        pii stuck=st[i].query(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;
          auto p=upper_bound(inds[j].begin(),inds[j].end(),last);
          while(p!=inds[j].end()&&*p<=y){
            // cerr<<"add "<<last+1<<' '<<(*p)-1<<" because "<<j<<'\n';
            trans({last+1,(*p)-1},did,val);
            last=*p;
            p++;
          }
          trans({last+1,y},did,val);
        }
      }
    }
    // cerr<<'\n';
  }
  // for(int i=0;i<n;i++){
  //   int dp[n][n]{};
  //   for(int sz=n;sz;sz--){
  //     for(int l=0;l<=n-sz;l++){
  //       int r=l+sz-1;
  //       if(updp[i][l][r]<=downdp[i][l][r]){
  //         dp[l][r]=(r-l+1)*(downdp[i][l][r]-updp[i][l][r]+1);
  //       }
  //       if(l&&dp[l-1][r]){
  //         dp[l][r]=max(dp[l][r],
  //           dp[l-1][r]+(r-l+1)*(downdp[i][l][r]-downdp[i][l-1][r]+updp[i][l-1][r]-updp[i][l][r]));
  //       }
  //       if(r+1<n&&dp[l][r+1]){
  //         dp[l][r]=max(dp[l][r],
  //           dp[l][r+1]+(r-l+1)*(downdp[i][l][r]-downdp[i][l][r+1]+updp[i][l][r+1]-updp[i][l][r]));
  //       }
  //     }
  //   }
  //   for(int i=0;i<n;i++){
  //     for(int j=0;j<n;j++){
  //       ans=max(ans,dp[i][j]);
  //     }
  //   }
  // }
  return ans;
}

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