Submission #1101990

#TimeUsernameProblemLanguageResultExecution timeMemory
1101990Mike_VuBali Sculptures (APIO15_sculpture)C++14
100 / 100
82 ms608 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double dou; #define pii pair<int, int> #define fi first #define se second #define pb push_back #define MASK(x) (1LL<<(x)) #define BITj(x, j) (((x)>>(j))&1) template<typename T> bool maximize(T &x, const T &y) { if (x < y) {x = y; return 1;} return 0; } template<typename T> bool minimize(T &x, const T &y) { if (x > y) {x = y; return 1;} return 0; } const int maxn = 2005, lg = 60; int n, l, r; ll a[maxn], ps[maxn]; namespace sub4{ const int maxn1 = 105; bool dp[maxn1][maxn1]; bool check(ll mask) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { ll sum = ps[i]-ps[j]; if ((sum&mask)==sum && (sum|mask)==mask) { //satisfied for (int seg = 1; seg <= i; seg++) { dp[i][seg] |= dp[j][seg-1]; } } } } for (int seg = l; seg <= r; seg++) { if (dp[n][seg]) return 1; } return 0; } void solve() { ll ans = MASK(lg)-1; for (int j = lg-1; j >= 0; j--) { if (check(ans^MASK(j))) ans ^= MASK(j); } cout << ans; } } namespace sub5{ int dp[maxn]; bool check(ll mask) { memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { ll sum = ps[i]-ps[j]; if ((sum&mask)==sum && (sum|mask)==mask) { //satisfied minimize(dp[i], dp[j]+1); } } } return (dp[n] <= r); } void solve() { ll ans = MASK(lg)-1; for (int j = lg-1; j >= 0; j--) { if (check(ans^MASK(j))) ans ^= MASK(j); } cout << ans; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); // #define name "task" // if (fopen(name".inp", "r")) { // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); // } cin >> n >> l >> r; ps[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; ps[i] = ps[i-1] + a[i]; } if (l == 1) return sub5::solve(), 0; return sub4::solve(), 0; } /* 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...