oj.uz

Submission #999585

# Submission time Handle Problem Language Result Execution time Memory
999585 2024-06-15T20:48:08 Z I_FloPPed21 Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 2396 KB 
#include <iostream>

using namespace std;

int n, a, b;
long long v[300005];

long long dp[2005][2005];
long long pd[2005];
void solve2()
{
    long long val = 0;

    long long tot = 0 ;
    for ( long long i = 63; i >= 0 ; i -- )
    {
        tot |= ( 1ll << i ) ;
    }
    for ( long long i = 63; i >= 0 ; i -- )
    {
        tot -= ( 1ll << i );
        for ( int j = 0; j <= n ; j ++ )
        {
            pd[j] = 1e9 ;
            if( a != 1 )
            for (int k = 0; k <= n ; k ++ )
                dp[j][k] = false ;
        }
        dp[0][0] = true ;
        pd[0] = 0 ;
        for ( int j = 1; j <= n; j ++ )
        {
            long long sum = 0 ;
            for ( int k = j ; k >= 1; k -- )
            {
                sum += v[k];

                long long cot = ( sum & tot ) ;
                long long vot = sum - cot ;
                if ( (val | vot) == val && ( pd[k-1] != 1e9 || ( k - 1 == 0 ))  )
                {
                    // cout << j << " " << k << '\n';


                        pd[j] = min ( pd[j] ,pd[k-1]+ 1);

                    if ( a != 1 )
                    for ( int t = 0; t <= b; t ++ )
                    {
                        if( dp[k-1][t] == true )
                            dp[j][t+1] = true ;
                    }
                }
            }
        }

        bool yes = false;
        if( a != 1 )
        for ( int d = a ; d <= b ; d ++  )
        {
            if ( dp[n][d] == true )
            {
                yes = true ;

            }
        }
        else
        {
            if ( pd[n] <= b  )
                {
                    yes = true ;
                    if( i == 3 )
                        cout << pd[n] << '\n';
                }
        }
        // cout << "YES" << '\n';
        if( yes == false )
            val |= ( 1ll << i);
    }
    cout << val << '\n';
}
int main()
{
    cin>> n >> a >> b;
    for( int i = 1; i <= n ; i ++ )
    {
        cin >> v[i];
    }
    solve2();
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 0 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -