Problem Description
A of length
n. He defines a function
fl,r,k where
l,r,k are positive integers that satisfies
l≤r and
r×k≤n, and the value of the function equals to
p×q×⌊k√⌋ where
p equals to the sum value of
Al×k,A(l+1)×k,...,Ar×k and
q equals to the minimal value of them. YJQQQAQ wants to choose the positive integers
l,r,k carefully to maximize the value of the function.
Input
T(1≤T≤3)——The number of the test cases. For each test case:
The first line contains an integers
n(1≤n≤300,000).
The second line contains
n integers describing the given array
A, the
ith integer is
Ai(1≤Ai≤1,000,000). Between each two adjacent integers there is a white space separated.
Output
For each test case, the only line contains the only integer that is the maximum value of the function.
Sample Input
1
3
2 3 1 Sample Output
Hint
原來有種東西叫做單調棧
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef __int64 LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int T, n, m, a[maxn], b[maxn], l[maxn], r[maxn];
LL sum[maxn];
int main() {
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
LL ans = 0;
for (int i = 1; i <= n; i++)
{
sum[0] = m = 0;
for (int j = 1; j*i <= n; j++)
{
b[++m] = a[j*i];
sum[m] = sum[m - 1] + b[m];
}
stack<int> p;
for (int j = 1; j <= m; j++)
{
while (!p.empty() && b[p.top()] > b[j]) r[p.top()] = j - 1, p.pop();
p.push(j);
}
while (!p.empty()) r[p.top()] = m, p.pop();
for (int j = m; j; j--)
{
while (!p.empty() && b[p.top()] > b[j]) l[p.top()] = j + 1, p.pop();
p.push(j);
}
while (!p.empty()) r[p.top()] = 1, p.pop();
for (int j = 1; j <= m; j++) ans = max(ans, (sum[r[j]] - sum[l[j] - 1])*b[j] * (int)sqrt(i));
}
printf("%I64d\n", ans);
}
return 0;
}