Submission #1194605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194605		Ak_16	Soccer Stadium (IOI23_soccer)	C++20	48 / 100	19 ms	11336 KiB

soccer

#include <iostream>
#include <vector>
using namespace std;

int pos[40][40];
int dp[35][35][35][35];
int mx[35][35][35][35];
int sm[35][35][35];
int fin;
int fi,fj,fk,fl;

int biggest_stadium(int n, vector<vector<int>> f){
  
  for(int i=0; i<30; i++){
    for(int j=0; j<30; j++){
      pos[i][j]=1;
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      pos[i][j] = f[i][j];
    }
  }
  
  n = 30;
  
  for(int i=0; i<30; i++){
    for(int j=0; j<30; j++){
      for(int k=0; k<30; k++){
        for(int l=0; l<30; l++){
          dp[i][j][k][l] = 0;
          mx[i][j][k][l] = 0;
        }
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      for(int k=j; k<n; k++){
        if(j==k){sm[i][j][k] = pos[i][j];}
        else {
          sm[i][j][k] = sm[i][j][k-1] + pos[i][k];
        }
      }
    }
  }
  
  for(int pl1=0; pl1<n; pl1++){
    for(int i=0; i<n-pl1; i++){
      for(int pl2=n-1; pl2>=0; pl2--){
        for(int j=0; j<n-pl2; j++){
          
          if(pl1==0){
            if(sm[i][j][j+pl2]==0){
              dp[i][i][j][j+pl2] = pl2+1;
            }
          }
          
          else {
            if(sm[i][j][j+pl2]==0&&mx[i+1][i+pl1][j][j+pl2]>0){
              dp[i][i+pl1][j][j+pl2] = max(dp[i][i+pl1][j][j+pl2], pl2 + 1 + mx[i+1][i+pl1][j][j+pl2]);
              
            }
            
            if(sm[i+pl1][j][j+pl2]==0&&mx[i][i+pl1-1][j][j+pl2]>0){
              dp[i][i+pl1][j][j+pl2] = max(dp[i][i+pl1][j][j+pl2], pl2 + 1 + mx[i][i+pl1-1][j][j+pl2]);
            }
          }
          
          if(pl2==n-1){
            mx[i][i+pl1][j][j+pl2] = dp[i][i+pl1][j][j+pl2];
          }
          
          else if(j==0){
            mx[i][i+pl1][j][j+pl2] = max(mx[i][i+pl1][j][j+pl2+1], dp[i][i+pl1][j][j+pl2]);
          }
          
          else {
            mx[i][i+pl1][j][j+pl2] = mx[i][i+pl1][j-1][j+pl2];
            for(int k=j+pl2; k<n; k++){
              mx[i][i+pl1][j][j+pl2] = max(mx[i][i+pl1][j][j+pl2], dp[i][i+pl1][j][k]);
            }
          }
          
        }
      }
    }
  }
  
  fin = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<n; k++){
        for(int l=0; l<n; l++){
          if(dp[i][j][k][l]>fin){fin = dp[i][j][k][l]; fi = i; fj = j; fk = k; fl = l;}
        }
      }
    }
  }
  
  return fin;
  
}

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