HDU 1506 Largest Rectangle in a Histogram(dp)

タイトルリンク:HDU 1506 Largest Rectangle in a Histogram
各板について、Area=height[i]*(j-k+1)は、いずれかのx、j<=x<=k、height[x]>=height[i];jを探して、kは肝心になります.
ダイナミックプランニングを使用して、左の高さがそれ自体に等しい場合、左の左境界は必ずこの性質を満たし、この境界の左から反復します.左境界を反復して右境界を反復します.
杭電で何度もTLEを提出して、c++の入出力はcの入出力に変えて、long long、_int 64は提出を変えて、どうしてもだめで、最後に提出方式をg++からc++に変更しました.過ぎました...

#include <iostream>

using namespace std;

const int MAX_N = 100000 + 100;

long long arr[MAX_N];
//__int64 arr[MAX_N];
int l[MAX_N],r[MAX_N];
int n;

int main()
{
    while(cin >> n,n)
    {
        for(int i = 1;i <= n;i++)
        {
            cin >> arr[i];
            l[i] = r[i] = i;
        }
        for(int i = 1;i <= n;i++)
        {
            while(l[i] - 1 > 0 && arr[l[i] - 1] >= arr[i])
            {
                l[i] = l[l[i] - 1];
            }
        }
        for(int i = n;i > 0;i--)
        {
            while(r[i] + 1 <= n && arr[r[i] + 1] >= arr[i])
            {
                r[i] = r[r[i] + 1];
            }
        }
        long long _max = 0;
        //__int64 _max = 0;
        for(int i = 1;i <= n;i++)
            _max = max(_max,(r[i] - l[i] + 1) * arr[i]);
        cout << _max << endl;
    }
    return 0;
}