Submission #1240620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240620		noyancanturk	Soccer Stadium (IOI23_soccer)	C++17	64 / 100	1394 ms	2162688 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 updp[n][n][n],downdp[n][n][n];
  for(int i=0;i<n;i++){
    for(int l=0;l<n;l++){
      int seen=0;
      for(int r=l;r<n;r++){
        seen+=a[i][r];
        if(seen)updp[i][l][r]=i+1;
        else if(!i)updp[i][l][r]=0;
        else updp[i][l][r]=updp[i-1][l][r];
      }
    }
  }
  for(int i=n-1;0<=i;i--){
    for(int l=0;l<n;l++){
      int seen=0;
      for(int r=l;r<n;r++){
        seen+=a[i][r];
        if(seen)downdp[i][l][r]=i-1;
        else if(i==n-1)downdp[i][l][r]=n-1;
        else downdp[i][l][r]=downdp[i+1][l][r];
      }
    }
  }
  int ans=0;
  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: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 22 / 22
• Subtask 4: 18 / 18
• Subtask 5: 16 / 16
• Subtask 6: 0 / 30