Submission #339488

#	Time	Username	Problem	Language	Result	Execution time	Memory
339488		blue	Bali Sculptures (APIO15_sculpture)	C++11	37 / 100	31 ms	492 KiB

sculpture

#include <iostream>
#include <vector>
using namespace std;

//Subtask 1, 2, 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
int solve_1(int N, int A, int B, vector<int> Y)
{
    // for(int y:Y) cout << y << ' ';
    // cout << '\n';


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

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

        dp[0][0] = 1;
        for(int i = 1; i <= N; i++)
        {
            dp[i][1] = (Y[i] | res) <= res;
            for(int x = 2; x <= B; x++)
            {
                for(int 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(int x = 1; x <= B; x++)
        // {
        //     for(int i = 1; i <= N; i++)
        //     {
        //         cout << dp[i][x] << ' ';
        //     }
        //     cout << '\n';
        // }

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


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

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

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

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

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

    vector<int> Y(N+1);
    Y[0] = 0;
    for(int 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 (stderr)

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

• Subtask 1: 0 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29