Submission #164747

#	Time	Username	Problem	Language	Result	Execution time	Memory
164747		quocnguyen1012	Bali Sculptures (APIO15_sculpture)	C++14	50 / 100	297 ms	4732 KiB

sculpture

#include <bits/stdc++.h>

#define Task "A"
#define pb push_back
#define int long long

using namespace std;
typedef long long ll;

mt19937 rng (chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2005;

int testbit (ll x, int n){
    return x >> n & 1;
}

int N;
int a[maxn];
ll sum[maxn];
ll dp[maxn];
int P, Q;

bool submask (ll mask1, ll mask2){
    return (mask1 & mask2) == mask1;
}

bool check (ll mask){
    for (int i=1; i<=N; ++i) dp[i] = 1e9;
    for (int i=1; i<=N; ++i){
        for (int j=i-1; j>=0; --j){
            if (dp[j] < 1e9 && submask (sum[i] - sum[j], mask)){
                dp[i] = min(dp[i], dp[j] + 1);
            }
        }
    }
    //cerr << f[N];
    return dp[N] <= Q;
}

int f[105][105][50];

ll solve (int l, int K){
    memset(f, -1, sizeof f);
    for (int i=1; i<=N; ++i){
        sum[i] = sum[i-1] + a[i];
        for (int j=0; j<=50; ++j){
            if (testbit (sum[i], j)) f[i][1][j] = sum[i];
        }
    }
    for (int i=2; i<=N; ++i){
        for (int j=2; j<=min(i, K); ++j){
            for (int z=0; z<=50; ++z){
                f[i][j][z] = 1e17;
                for (int t=i-1; t>=0; --t){
                    if (f[t][j-1][z] == -1) continue;
                    if (f[i][j][z] == -1) f[i][j][z] = f[t][j-1][z] | (sum[i] - sum[t]);
                    else
                        f[i][j][z] = min (f[i][j][z], f[t][j-1][z] | (sum[i] - sum[t]));
                }
            }
        }
    }
    ll ans = 1e15;
    for (int j=l; j<=K; ++j)
        for (int i=0; i<=35; ++i)
            if (f[N][j][i] != -1)
                ans = min (ans, f[N][j][i]);
    return ans;
}
signed main (void){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen (Task".inp", "r")){
        freopen (Task".inp", "r", stdin);
        freopen (Task".out", "w", stdout);
    }
    cin >> N >> P >> Q;
    for (int i=1; i<=N; ++i){
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    if (P == 1){
        ll ans = (1ll << 62) - 1;
        for (int i=61; i>=0; --i){
            if (check (ans -(1ll << i)))
                ans -= (1ll << i);
            ///cerr << ans << '\n';
        }
        cout << ans;
    }
    else{
        cout << solve(P, Q);
    }
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:74:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen (Task".inp", "r", stdin);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:75:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen (Task".out", "w", stdout);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp: In function 'll solve(long long int, long long int)':
sculpture.cpp:54:28: warning: iteration 50 invokes undefined behavior [-Waggressive-loop-optimizations]
                 f[i][j][z] = 1e17;
                 ~~~~~~~~~~~^~~~~~
sculpture.cpp:53:28: note: within this loop
             for (int z=0; z<=50; ++z){
                           ~^~~~

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