Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19580 Accepted Submission(s): 5921
- #include < cstdio > #include < algorithm > using namespace std;#define LL long long const int maxn = 100005;#ifdef WIN32#define lld "I64d"#
- else#define lld "lld"#endif
- int a[maxn],
- b[maxn];
- int l[maxn],
- r[maxn],
- tmp[maxn],
- q[maxn];
- int n,
- m;
- void work(int c[], int d[]) {
- q[1] = c[1];
- tmp[1] = 1;
- int head = 1,
- tail = 1;
- for (int i = 2; i <= n; ++i) {
- while (head <= tail && q[tail] > c[i]) d[tmp[tail--]] = i - 1;
- q[++tail] = c[i];
- tmp[tail] = i;
- }
- while (head <= tail) d[tmp[head++]] = n;
- }
- int main() {
- while (scanf("%d", &n) && n != 0) {
- LL ans = 0;
- for (int i = 1; i <= n; ++i) scanf("%d", a + i),
- b[n - i + 1] = a[i];
- work(a, r);
- work(b, l);
- for (int i = 1; i <= n; ++i) tmp[i] = l[i];
- for (int i = 1; i <= n; ++i) l[n - i + 1] = n - tmp[i] + 1;
- for (int i = 1; i <= n; ++i) ans = max(ans, 1ll * a[i] * (r[i] - l[i] + 1));
- printf("%lld\n", ans);
- }
- return 0;
- }
HUD 1506 Largest Rectangle in a Histogram
来源: http://www.bubuko.com/infodetail-2357736.html