算法競賽AcWing在線題庫_4395. 最大子矩陣
#include<iostream>??
#include<algorithm>
?using namespace std;
?/*?
?(a[i]+ a[i+1]+...+a[j])(b[s]+ b[s+1]+...+b[t])<=x
?求 (j - i + 1)*(t - s + 1) 最大
?*/
const int N = 2010;
int n=3, m=3, x=9;
int a[N]={0,1,2,3};
int b[N]={0,1,2,3};
int c[N * N];
int main() {
?/*
cin >> n >> m;
? ? for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
? ? for (int i = 1; i <= m; i++) cin >> b[i], b[i] += b[i - 1];
? ? cin >> x;?
*/
??
for (int i = 1; i <= n; i++)? ? a[i] += a[i - 1];
? ? for (int i = 1; i <= m; i++)? ?b[i] += b[i - 1];
? ? // 數(shù)組c[tar],表示和不超過tar子區(qū)間的最大長度
? ? for (int i = 1; i <= m; i++)
? ? ? ? for (int j = i; j <= m; j++)? ? ? ? ? ?
{ if (c[b[j] - b[i - 1]]<j - i + 1)c[b[j] - b[i - 1]]=j - i + 1;
cout<<b[j] - b[i - 1]<<"? "<<j - i + 1<<endl;
}
? ? for (int i = 1; i < N * m; i++) if (c[i]< c[i - 1])c[i]= c[i - 1];
? ? ? ??
cout << endl;
for (int i = 1; i <n * m; i++) cout<<c[i]<<"? "<<i<<endl;
cout << endl;
? ? int res = 0;
? ? for (int i = 1; i <= n; i++)
? ? ? ? for (int j = i; j <= n; j++) {
? ? ? ? ? ? int tar = x / (a[j] - a[i - 1]);?
cout<<tar<<"? "<<j - i + 1<<endl;
if (tar >= N * m) { if(res<(j - i + 1) * m)res= (j - i + 1) * m; }
? ? ? ? ? ? else?
if(res< c[tar] * (j - i + 1))res= c[tar] * (j - i + 1);
? ? ? ? }
? ? cout << res<<endl;
}