oj.uz

Submission #125399

# Submission time Handle Problem Language Result Execution time Memory
125399 2019-07-05T08:03:48 Z acebroad Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 2 ms 376 KB 
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

typedef long long ll;

ll n, a, b;
ll arr[2005];

//ll pow2(int p) {
//    ll v = 1;
//    for(int i = 0; i < p; i++) v *= 2;
//    return v;
//}

int main() {
    cin >> n >> a >> b;
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    ll p = 0;
    ll divs = 0;
    ll sum = 0;
    while (true) {
        divs = 0;
        sum = 0;
        ll m = 1LL << p;
        bool success = true;
        for (int i = 0; i < n; i++) {
            if (sum + arr[i] < m) sum += arr[i];
            else {
                if (divs >= b) {
                    success = false;
                    break;   
                } else {
                    divs++;
                    sum = arr[i];
                }
            }
        }
        
        if (success && divs >= a) {
            break;
        }
        
        p++;
    }
    
//    printf("%lld\n", pow2(p));

    ll map = 0;
    map |= 1LL << (p - 1);
    ll cur = p - 2;
    
    while (cur >= 0) {
        divs = 1;
        sum = 0;
        bool success = true;
        int i = 0;
        ll lastsum = 0;
        ll lasti = 0;
        bool firstfail = true;
        while(i < n) {
            lastsum = sum;
            sum = sum + arr[i];
            
//            if (sum > map) {
//                success = false;
//                break;
//            }
            
            for(ll j = cur; j < 64; j++) {
                // bit violence
                if (!(map & (1LL << j)) && (sum & (1LL << j))) {
                    if (firstfail) {
                        firstfail = false;
                        lasti = i;
                        lastsum = sum;
                    }
                    
                    if (sum > map) {
//                        cout << "div/ " << map << " " << divs << " " << sum << " " << lastsum << " " << j << endl;
                        divs++;
                        sum = sum - lastsum;
                        i = lasti - 1;
                        firstfail = true;
                        break;
                    }
//                    divs++;
//                    sum = arr[i];
//                    break;
                }
            }
            
            if (divs > b) {
                success = false;
//                cout << "too many divs\n";
                break;
            }
            // bit violence
//            if ((nsum ^ map) & ~((1 << (p-2)) - 1)) {
//                
//            }
            i++;
        }

        for(ll j = cur; j < 64; j++) {
            // bit violence
            if (!(map & (1LL << j)) && (sum & (1LL << j))) {
                success = false;
                break;
            }
        }
        
//        cout << success << " " << divs << " " << map << " " << cur << endl;
        if (!success || divs < a || divs > b) {  
//            cout << "fail/ " << success << " " << divs << endl;
            map |= 1 << cur;
        }
        
        cur--;
    }
    
    cout << map << '\n';
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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