Submission #577868

#	Time	Username	Problem	Language	Result	Execution time	Memory
577868		MohamedFaresNebili	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	90 ms	468 KiB

sculpture

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
        using pi = array<int, 3>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define all(x) (x).begin(), (x).end()
        #define int ll
        #define lb lower_bound
        #define ub upper_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        const int oo = 1e15 + 7;

        int N, A, B, res;
        int arr[2001], DP[101][101], dp[2001], P[50];
        int solve(int i, int j) {
            if(i == N) {
                if(j >= A && j <= B) return 1;
                return 0;
            }
            if(DP[i][j] != -1) return DP[i][j];
            int best = 0; int curr = 0;
            for(int l = i; l < N; l++) {
                curr += arr[l];
                if(curr & res) continue;
                best |= solve(l + 1, j + 1);
            }
            return DP[i][j] = best;
        }
        int solve(int i) {
            if(i == N) return 0;
            if(dp[i] != -1) return dp[i];
            int best = oo, curr = 0;
            for(int l = i; l < N; l++) {
                curr += arr[l];
                if(curr & res) continue;
                best = min(best, 1 + solve(l + 1));
            }
            return dp[i] = best;
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> A >> B;
            for(int l = 0; l < N; l++)
                cin >> arr[l];
            int curr = 1;
            for(int l = 0; l <= 50; l++)
                P[l] = curr, curr *= 2;
            for(int l = 49; l >= 0; l--) {
                res += P[l];
                if(N <= 100) {
                    memset(DP, - 1, sizeof DP);
                    if(!solve(0, 0)) res -= P[l];
                }
                if(N > 100) {
                    memset(dp, -1, sizeof dp);
                    if(solve(0) > B) res -= P[l];
                }
            }
            cout << P[50] - 1 - res << "\n";
            return 0;
        }

Compilation message (stderr)

sculpture.cpp: In function 'int32_t main()':
sculpture.cpp:63:22: warning: iteration 50 invokes undefined behavior [-Waggressive-loop-optimizations]
   63 |                 P[l] = curr, curr *= 2;
      |                 ~~~~~^~~~~~
sculpture.cpp:62:30: note: within this loop
   62 |             for(int l = 0; l <= 50; l++)
      |                            ~~^~~~~
sculpture.cpp:75:25: warning: array subscript 50 is above array bounds of 'll [50]' {aka 'long long int [50]'} [-Warray-bounds]
   75 |             cout << P[50] - 1 - res << "\n";
      |                     ~~~~^
sculpture.cpp:29:48: note: while referencing 'P'
   29 |         int arr[2001], DP[101][101], dp[2001], P[50];
      |                                                ^

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