hdu 3530 단일 대기열 최적화 DP

AC 코드는 다음과 같습니다.
#include 
#include 
#include 
#include 
using namespace std;

int q1[211000], pos1[211000], head1, tail1;
int q2[211000], pos2[211000], head2, tail2;
int ans, now;
int N, M, K;
int num[211000];

int main(){
    while( scanf( "%d%d%d", &N, &M, &K ) != EOF ){
        for( int i = 1; i <= N; i++ ){
            scanf( "%d", &num[i] );
        }
        head1 = head2 = 0;
        tail1 = tail2 = -1;
        ans = 0;
        now = 0;
        for( int i = 1; i <= N; i++ ){
            now++;
            while( head1 <= tail1 && num[i] > q1[tail1] )    tail1--;
            q1[++tail1] = num[i];pos1[tail1] = i;
            while( head2 <= tail2 && num[i] < q2[tail2] )    tail2--;
            q2[++tail2] = num[i];pos2[tail2] = i;

            while( q1[head1] - q2[head2] > K ){
                if( pos1[head1] < pos2[head2] ){
                    now = i - pos1[head1];
                    head1++;
                }else{
                    now = i - pos2[head2];
                    head2++;
                }
            }
            if( q1[head1] - q2[head2] >= M ){
                ans = max( ans, now );
            }
        }
        cout << ans << endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기