제출 #1349452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1349452		samuelandrianoo_	Bali Sculptures (APIO15_sculpture)	C++20	37 / 100	10 ms	2116 KiB

sculpture

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

int main(){
        ios_base::sync_with_stdio(false); cin.tie(NULL);

        ll n, A, B; cin >> n >> A >> B;
        ll arr[n + 5], pref[n + 5]; for (ll i = 1; i <= n; i++) cin >> arr[i]; memset(pref, 0, sizeof(pref));
        for (ll i = 1; i <= n; i++) pref[i] = pref[i - 1] + arr[i];

        if (A == 1){
                ll dp[105][2005]; for (ll i = 0; i <= 100; i++){ for (ll j = 0; j <= 2000; j++) dp[i][j] = 1e9;}; //dp (idx, curOR) = groups
                dp[0][0] = 0;
                for (ll i = 1; i <= n; i++){
                        for (ll j = 0; j <= 2000; j++){
                                for (ll bck = 0; bck < i; bck++){
                                        if (dp[bck][j] != 1e9) dp[i][(j | (pref[i] - pref[bck]))] = min(dp[bck][j] + 1, dp[i][(j | (pref[i] - pref[bck]))]);
                                }
                        }
                }

                ll mcn = 1e9;

                for (ll j = 0; j <= 2000; j++){
                        if (dp[n][j] <= B) mcn = min(mcn, j);
                }

                cout << mcn << endl;

        } else {
                bool dp[55][25][505]; memset(dp, 0, sizeof(dp)); //dp (idx, groups, curOR) = yes/no
                ll mcn = 1e9;
                dp[0][0][0] = 1;
                for (ll i = 1; i <= n; i++){
                        for (ll j = 1; j <= B; j++){
                                for (ll z = 0; z <= 500; z++){
                                        for (ll bck = 0; bck < i; bck++){
                                                if (dp[bck][j - 1][z]){
                                                        dp[i][j][z | (pref[i] - pref[bck])] = 1;
                                                        if (j >= A && i == n) mcn = min((z | (pref[i] - pref[bck])), mcn);
                                                }
                                        }
                                }
                        }
                }
                cout << mcn << endl;
        }
}

/*

*/

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