제출 #1321530

#제출 시각아이디문제언어결과실행 시간메모리
1321530AMel0nBali Sculptures (APIO15_sculpture)C++20
100 / 100
63 ms472 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; ll N, A, B; vector<ll> V; vector<ll> PS; ll sum(ll a, ll b) { return PS[b+1] - PS[a]; } signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> A >> B; V.resize(N), PS.resize(N+1); ll UB = 0; for(ll i = 0; i < N; i++) { cin >> V[i]; PS[i+1] = PS[i] + V[i]; UB += V[i]; } if (A == 1) { UB = __lg(UB); ll cur = (1ll << UB+1ll) - 1ll; for(ll k = UB; k >= 0; k--) { cur ^= (1ll << k); vector<ll> dp(N+1, INF); // dp[i] = min # of partitions dp[0] = 0; for(ll i = 0; i <= N; i++) { for(ll j = 0; j < i; j++) { if ((cur | sum(j, i-1)) == cur) { dp[i] = min(dp[i], 1 + dp[j]); } } } if (dp[N] > B) cur ^= (1ll << k); } cout << cur << endl; } else { UB = __lg(UB); ll cur = (1ll << UB+1ll) - 1ll; for(ll k = UB; k >= 0; k--) { cur ^= (1ll << k); vector<vector<bool>> dp(N+1, vector<bool>(B+1)); // dp[i][# of partitions] dp[0][0] = true; for(ll i = 0; i <= N; i++) { for(ll j = 0; j < i; j++) { for(ll k = 1; k <= B; k++) { dp[i][k] = dp[i][k] | (dp[j][k-1] & ((cur | sum(j, i-1)) == cur)); } } } bool yes = false; for(ll k = A; k <= B; k++) { if (dp[N][k]) yes = true; } if (!yes) cur ^= (1ll << k); } cout << cur << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...