oj.uz

Submission #167020

# Submission time Handle Problem Language Result Execution time Memory
167020 2019-12-05T09:30:01 Z Hideo Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 10 ms 376 KB 
// Need to git gud and reach 1900+
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define prev prev123
#define next next123
#define pow pow123
#define left left123
#define right right123

const int N = 2007;
const int INF = 1e9 + 7;

ll a[N];
int n, x, y;

main(){ // If you don't know what to do, check the text box at the bottom
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    ll mask = 0;
    if (x == 1){
        int dp[N];
        dp[0] = 0;
        for (ll j = 45; j >= 0; j--){
            ll submask = (mask | (1LL << j)), s = 0;
            for (int i = 1; i <= n; i++){
                s = 0; dp[i] = INF;
                for (int l = i; l >= 1; l--){
                    s += a[l];
                    if (!(s & submask))
                        dp[i] = min(dp[l - 1] + 1, dp[i]);
                }
            }
            if (dp[n] < y)
                mask = submask;
        }
    }
    else {
        bool dp[107][107];
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (ll j = 45; j >= 0; j--){
            ll submask = (mask | (1LL << j)), s = 0;
            for (int i = 1; i <= n; i++){
                dp[i][0] = false;
                for (int g = 1; g <= min(i, y); g++){
                    dp[i][g] = false;
                    s = 0;
                    for (int l = i; l >= g; l--){
                        s += a[l];
                        if (s & submask)
                            continue;
                        dp[i][g] |= dp[l - 1][g - 1];
                    }
                }
            }
            bool b = false;
            for (int i = x; i <= y; i++){
                if (dp[n][i]){
                    b = true;
                    break;
                }
            }
            if (b)
                mask = submask;
        }
    }
    printf("%lld", (mask ^ ((1LL << 46) - 1)));

}

/*
    Totally not inspired by BenQ's template
    Things you should do:
    1. Look for stupid typos in code e.g 1 instead of -1 etc
    2. Check if there is no infinite loops
    3. "Measure twice, cut once"
    4. Stay focused
*/

Compilation message

sculpture.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){ // If you don't know what to do, check the text box at the bottom
      ^
sculpture.cpp: In function 'int main()':
sculpture.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -