제출 #125396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125396		acebroad	Bali Sculptures (APIO15_sculpture)	C++17	0 / 100	2 ms	380 KiB

sculpture

#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 ans = 1LL << (p - 1);
    ll map = 0;
    map |= 1LL << (p - 1);
    ll cur = p - 2;
    
    while (cur >= 0) {
        divs = 1;
        sum = 0;
        bool success = true;
        ll lastsum = 0;
        for(int i = 0; i < n; i++) {
            
            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 (sum > map) {
//                        cout << "div/ " << map << " " << divs << " " << sum << " " << lastsum << " " << j << endl;
                        divs++;
                        sum = sum - lastsum;
                        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)) {
//                
//            }
        }

        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';
}

컴파일 시 표준 에러 (stderr) 메시지

sculpture.cpp: In function 'int main()':
sculpture.cpp:51:8: warning: unused variable 'ans' [-Wunused-variable]
     ll ans = 1LL << (p - 1);
        ^~~

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