oj.uz

Submission #339489

# Submission time Handle Problem Language Result Execution time Memory
339489 2020-12-25T13:49:23 Z blue Bali Sculptures (APIO15_sculpture) C++11
0 / 100
 1 ms 364 KB 
#include <iostream>
#include <vector>
using namespace std;

//Subtask 1, 2, 3, 4: N <= 100
/*
For the worst beauty value, we want to first of all make the most significant bit as small as possible.

Loop through all the bits: log(max_N)    =  32
Loop through all the positions:     N    =  100
Loop through all the previous choices: N =  100
Loop through all the choices of x (a<x<b)=  100
Grand total                              = 32e6 = 3e7 √
*/

//     arr size,   limits on x,   sculpture values
long long solve_1(long long N, long long A, long long B, vector<long long> Y)
{
    // for(long long y:Y) cout << y << ' ';
    // cout << '\n';


    long long dp[N+1][B+1]; //is it possible to partition 1..i long longo j groups such that no group has value v & 1<<bit == 1
    long long res = (1LL << 35) - 1, temp;   //fix this number
    long long curr_res = 0;
    for(long long bit = 34; bit >= 0; bit--) //fix this number
    {
        // cout << "bit = " << bit << '\n';
        for(long long i = 0; i <= N; i++) for(long long x = 0; x <= B; x++) dp[i][x] = 0;
        res -= (1 << bit);

        // cout << "res = " << res << '\n';

        dp[0][0] = 1;
        for(long long i = 1; i <= N; i++)
        {
            dp[i][1] = (Y[i] | res) <= res;
            for(long long x = 2; x <= B; x++)
            {
                for(long long j = 0; j < i; j++)
                {
                    if(((Y[i] - Y[j]) | res) > res) continue;
                    if(!dp[j][x-1]) continue;
                    // cout << i << ' ' << x << ' ' << j << ' ' << Y[i] - Y[j] << ' ' << res << '\n';
                    dp[i][x] |= dp[j][x-1];
                }
            }
        }

        // for(long long x = 1; x <= B; x++)
        // {
        //     for(long long i = 1; i <= N; i++)
        //     {
        //         cout << dp[i][x] << ' ';
        //     }
        //     cout << '\n';
        // }

        temp = 0;
        for(long long x = A; x <= B; x++) temp |= dp[N][x];
        if(!temp) res += (1 << bit);


        // cout << "______________________\n";
    }
    return res;
}

/*
-----------------------------------------------------
*/

//Subtask 3, 5: A = 1
/*

*/
long long solve_2(long long N, long long B, vector<long long> Y)
{
    return 0;
}

int main()
{
    long long N, A, B;
    cin >> N >> A >> B;

    vector<long long> Y(N+1);
    Y[0] = 0;
    for(long long i = 1; i <= N; i++)
    {
        cin >> Y[i];
        Y[i] += Y[i-1];
    }

    /*if(N <= 100)*/cout << solve_1(N, A, B, Y) << '\n';
    //else cout << solve_2(N, B, Y) << '\n'; //A = 1
}

Compilation message

sculpture.cpp: In function 'long long int solve_1(long long int, long long int, long long int, std::vector<long long int>)':
sculpture.cpp:25:15: warning: unused variable 'curr_res' [-Wunused-variable]
   25 |     long long curr_res = 0;
      |               ^~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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