Submission #340139

#	Time	Username	Problem	Language	Result	Execution time	Memory
340139		blue	Bali Sculptures (APIO15_sculpture)	C++11	21 / 100	154 ms	508 KiB

sculpture

#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 √
*/

long long pow2[40];

//     arr size,   limits on x,   sculpture values
long long solve_1(long long N, long long A, long long B, vector<long long> Y)
{
    long long 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
    long long res = pow2[39] - 1, temp;
    long long curr_res = 0;
    for(long long bit = 38; bit >= 0; bit--)
    {
        for(long long i = 0; i <= N; i++) for(long long x = 0; x <= B; x++) dp[i][x] = 0;
        res -= pow2[bit];

        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;
                    dp[i][x] |= dp[j][x-1];
                }
            }
        }

        temp = 0;
        for(long long x = A; x <= B; x++) temp |= dp[N][x];
        if(!temp) res += pow2[bit];
    }
    return res;
}
/*
-----------------------------------------------------
*/

//Subtask 3, 5: A = 1
/*
We start out with Y[1] + ... Y[N]
We can make a cut anywhere between i and i+1, which turns a+b into a | b
We can make at most B cuts.
Find the minimum value.
(a | b) | c = a | b | c
                           only difference is here.
    00      10      01      11
+    0       1       1       2
|    0       1       1       1



Greedy?
8 1 2 1 5 4
1000, 0001, 0010, 0001, 0101, 0100
Prefsum:
8 9 11 12 17 21
001000, 001001, 001011, 001100, 010001, 010101
*/
long long solve_2(long long N, long long B, vector<long long> Y)
{
    long long dp[N+1]; //minimum number of partitions of 1..i such that no group has value v & 1<<bit == 1
    long long res = pow2[39] - 1, temp;
    long long curr_res = 0;
    for(long long bit = 38; bit >= 0; bit--)
    {
        res -= pow2[bit];

        dp[0] = 0;
        for(long long i = 1; i <= N; i++)
        {
            dp[i] = B+1;
            for(long long j = 0; j < i; j++)
            {
                if(((Y[i] - Y[j]) | res) > res) continue;
                dp[i] = min(dp[i], dp[j]+1);
            }
        }

        if(dp[N] > B) res += pow2[bit];
    }
    return res;
}




int main()
{
    pow2[0] = 1;
    for(int i = 1; i < 40; i++) pow2[i] = pow2[i-1] * 2;

    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

cout << solve_2(N, B, Y) << '\n';
}

Compilation message (stderr)

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:24:15: warning: unused variable 'curr_res' [-Wunused-variable]
   24 |     long long curr_res = 0;
      |               ^~~~~~~~
sculpture.cpp: In function 'long long int solve_2(long long int, long long int, std::vector<long long int>)':
sculpture.cpp:79:35: warning: unused variable 'temp' [-Wunused-variable]
   79 |     long long res = pow2[39] - 1, temp;
      |                                   ^~~~
sculpture.cpp:80:15: warning: unused variable 'curr_res' [-Wunused-variable]
   80 |     long long curr_res = 0;
      |               ^~~~~~~~

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