oj.uz

Submission #490568

# Submission time Handle Problem Language Result Execution time Memory
490568 2021-11-28T03:14:31 Z DeadlyCritic Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 0 ms 208 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize("no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())

// #define c0 (v << 1)
// #define c1 (c0 | 1)
// #define md ((l+r)>>1)

using namespace std;

typedef long long ll;
const int maxN = 1e2+7;

ll pef[maxN];
int y[maxN];
bool dp[maxN][maxN];

inline ll range(int l, int r){
    return pef[r+1]-pef[l];
}

signed main(){IOS

    int n;
    int a, b;
    cin >> n >> a >> b;
    for(int i = 0; i < n; i++){
        cin >> y[i];
    }

    assert(n < maxN);

    ll ans = 0;
    ll bads = 0;

    pef[0] = 0;
    for(int i = 0; i < n; i++)pef[i+1] = pef[i]+y[i];

    int maxAns = 1ll << 40;

    for(int bit = 40; bit >= 0; bit--){
        bads += (1ll << bit);

        for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)dp[i][j] = 0;
        for(int i = a; i <= b; i++)dp[0][i] = 1;

        for(int i = 0; i < n; i++){
            for(int k = 0; k < b; k++){
                for(int j = 0; j <= i; j++){
                    if(range(j, i) < maxAns && (range(j, i) & bads) == 0){
                        dp[i+1][k] |= dp[j][k+1];
                    }
                }
            }
        }

        if(dp[n][0] == 0){
            bads -= (1 << bit);
            ans += (1 << bit);
        }
    }

    cout << ans << '\n';
    

}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:47:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '1099511627776' to '0' [-Woverflow]
   47 |     int maxAns = 1ll << 40;
      |                  ~~~~^~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 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 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

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