Submission #478444

#TimeUsernameProblemLanguageResultExecution timeMemory
478444arujbansalBali Sculptures (APIO15_sculpture)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; #define int long long using ll = long long; const int MXN = 1e2 + 1, MXA = 1e9 + 1, MXK = 50, INF = 1e18; int dp[MXN][MXN][MXK]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, X, Y; cin >> N >> X >> Y; int A[N]; for (int i = 1; i <= N; i++) cin >> A[i]; for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) for (int k = 0; k < MXK; k++) dp[i][j][k] = INF; for (int k = 0; k < MXK; k++) dp[0][0][k] = 0; for (int group = 1; group <= N; group++) { for (int i = 1; i <= N; i++) { for (int j = i, sum = 0; j >= 1; j--) { sum += A[j]; int pos = 0; for (int bit = MXK - 1; bit >= 0; bit--) { if ((sum >> bit) == 1) { pos = bit; break; } } for (int bit = pos; bit >= 0; bit--) dp[group][i][pos] = min(dp[group][i][pos], dp[group - 1][j - 1][bit] | (1LL << pos) | sum); } } } int ans = INF; for (int group = X; group <= Y; group++) for (int bit = 0; bit < MXK; bit++) ans = min(ans, dp[group][N][bit]); cout << ans; } /* 6 1 3 8 1 2 1 5 4 */
#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...