Submission #869955

#	Time	Username	Problem	Language	Result	Execution time	Memory
869955		chonka	Giraffes (JOI22_giraffes)	C++98	59 / 100	7096 ms	600 KiB

giraffes

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int MAXN = 8007 ;

int n ;
int a[ MAXN ] ;

int dp[ MAXN ][ 4 ] ;
int nw[ MAXN ][ 4 ] ;

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 0 ; j < 4 ; ++ j ) {
            dp[ i ][ j ] = 0 ;
            nw[ i ][ j ] = MAXN ; 
        }
    }
    for ( int len = 2 ; len <= n + 1 ; ++ len ) {
        bool done = true ;
        for ( int i = 1 ; i <= n ; ++ i ) {
            bool done1 = false , done2 = false ;
            for ( int t = i - 1 ; t >= 1 ; -- t ) {
                int id ;
                if ( i - t > a[ i ] - 1 ) { done2 = true ; }
                if ( i - t > n - a[ i ] ) { done1 = true ; }
                if ( done1 == true && done2 == true ) { break ; }
                if ( a[ t ] < a[ i ] ) {
                    id = 3 ;
                    if ( done2 == true ) { continue ; }
                }
                else {
                    id = 2 ;
                    if ( done1 == true ) { continue ; }
                }
                int dx = i - t , dy = abs ( a[ i ] - a[ t ] ) ;
                if ( dp[ t ][ id ^ 3 ] < min ( dx , dy ) ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy ) ) ;
                }
                if ( dp[ t ][ id ^ 2 ] < dx ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy + dp[ t ][ id ^ 2 ] ) ) ;
                }
                if ( dp[ t ][ id ^ 1 ] < dy ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dy , dx + dp[ t ][ id ^ 1 ] ) ) ;
                }
                nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy ) + dp[ t ][ id ] ) ;
                if ( dx > nw[ i ][ 2 ] && dx > nw[ i ][ 3 ] ) { break ; }
            }
            done1 = false , done2 = false ;
            for ( int t = i + 1 ; t <= n ; ++ t ) {
                int id ;
                if ( t - i > a[ i ] - 1 ) { done2 = true ; }
                if ( t - i > n - a[ i ] ) { done1 = true ; }
                if ( done1 == true && done2 == true ) { break ; }
                if ( a[ t ] < a[ i ] ) {
                    id = 1 ;
                    if ( done2 == true ) { continue ; }
                }
                else {
                    id = 0 ;
                    if ( done1 == true ) { continue ; }
                }
                int dx = t - i , dy = abs ( a[ i ] - a[ t ] ) ;
                if ( dp[ t ][ id ^ 3 ] < min ( dx , dy ) ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy ) ) ;
                }
                if ( dp[ t ][ id ^ 2 ] < dx ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy + dp[ t ][ id ^ 2 ] ) ) ;
                }
                if ( dp[ t ][ id ^ 1 ] < dy ) {
                    nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dy , dx + dp[ t ][ id ^ 1 ] ) ) ;
                }
                nw[ i ][ id ] = min ( nw[ i ][ id ] , max ( dx , dy ) + dp[ t ][ id ] ) ;
                if ( dx > nw[ i ][ 0 ] && dx > nw[ i ][ 1 ] ) { break ; }
            }
            if ( nw[ i ][ 0 ] > n - i || nw[ i ][ 0 ] > n - a[ i ] ) { nw[ i ][ 0 ] = MAXN ; }
            if ( nw[ i ][ 1 ] > n - i || nw[ i ][ 1 ] > a[ i ] - 1 ) { nw[ i ][ 1 ] = MAXN ; }
            if ( nw[ i ][ 2 ] > i - 1 || nw[ i ][ 2 ] > n - a[ i ] ) { nw[ i ][ 2 ] = MAXN ; }
            if ( nw[ i ][ 3 ] > i - 1 || nw[ i ][ 3 ] > a[ i ] - 1 ) { nw[ i ][ 3 ] = MAXN ; }
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            for ( int j = 0 ; j < 4 ; ++ j ) {
                dp[ i ][ j ] = nw[ i ][ j ] ;
                if ( dp[ i ][ j ] != MAXN ) { done = false ; }
                nw[ i ][ j ] = MAXN ; 
            }
        }
        if ( done == true ) {
            cout << n - ( len - 1 ) << "\n" ;
            return ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 41