Submission #147648

---

Source Code Expand

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

int main(){
  int N;
  cin >> N;
  int D[55][55];
  for(int i = 0 ; i < N ; i++)
    for(int j = 0 ; j < N ; j++) cin >> D[i][j];
 
  int sum[55][55];
  memset(sum, 0, sizeof(sum));
  
  for(int i = 0 ; i < N ; i++) sum[i][0] = D[i][0];
  
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < N-1 ; j++){
      sum[i][j+1] = sum[i][j] + D[i][j+1];
    }
  }
  
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < N ; j++){
      sum[j+1][i] += sum[j][i];      
    }
  }

  /*
  cout << endl;
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < N ; j++){
      cout << sum[i][j] << ' ';
    }
    cout << endl;
  }
  */
  int dp[55*55];
  memset(dp, 0, sizeof(dp));
  
  for(int i = 0 ; i < N ; i++){
    for(int j = 0 ; j < N ; j++){
      for(int k = i ; k < N ; k++){
	for(int l = j ; l < N ; l++){
	  int S = (k-i+1)*(l-j+1);	  
	  
	  int res = sum[k][l];
	  if(i != 0) res -= sum[i-1][l];
	  if(j != 0) res -= sum[k][j-1];
	  if(i != 0 && j != 0) res += sum[i-1][j-1];
	  
	  dp[S] = max(dp[S], res);
	}
      }
    }
  }
  
  //for(int i = 1 ; i <= N*N ; i++) cout << dp[i] << endl;
  
  int Q;
  cin >> Q;
  
  int x;
  while(Q--){
    cin >> x;
    int ans = 0;
    for(int i = 0 ; i <= x ; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
  }
  
  
  return 0;
}

Submission Info

Judge Result