Submission #7582268

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

int main(){
  
  int n;
  cin>>n;
  int d[n][n];
  REP(i,n){
    REP(j,n){
      cin>>d[i][j];
    }
  }
  int dsum[n][n];
  REP(i,n){
    REP(j,n){
      if(i==0 && j==0){
        dsum[i][j] = d[i][j];
      }else if(i==0){
        dsum[i][j] = dsum[i][j-1] + d[i][j];
      }else if(j==0){
        dsum[i][j] = dsum[i-1][j] + d[i][j];
      }else{
        dsum[i][j] = dsum[i-1][j] + dsum[i][j-1] - dsum[i-1][j-1] + d[i][j];
      }
    }
  }
  int max_area[n*n+1] = {};
  int temp;
  int now;
  bool flag;
  REPP(s,n*n){
    temp = 0;
    for(int a=1;a<=s;a++){
      if(s%a != 0)continue;
      int b = s/a;
      flag = true;
      REP(i,n){
        REP(j,n){
          if(i+a-1 >=n){
            flag = false;
            break;
          }
          if(j+b-1>=n)continue;
          if(i==0 && j==0){
            now = dsum[i+a-1][j+b-1];
          }else if(i==0){
            now = dsum[i+a-1][j+b-1] - dsum[i+a-1][j-1];
          }else if(j==0){
            now = dsum[i+a-1][j+b-1] - dsum[i-1][j+b-1];
          }else{
            now = dsum[i+a-1][j+b-1] - dsum[i-1][j+b-1] - dsum[i+a-1][j-1] + dsum[i-1][j-1];
          }
          temp = max(temp,now);
        }
      }
    }
    max_area[s] = max(max_area[s-1],temp);
  }
  
  int q;
  cin>>q;
  int p;
  REP(i,q){
    cin>>p;
    cout<<max_area[p]<<endl;
  }
  return 0;
}

Submission Info

Judge Result