Submission #388871

#TimeUsernameProblemLanguageResultExecution timeMemory
388871talant117408Bali Sculptures (APIO15_sculpture)C++17
9 / 100
88 ms460 KiB
/* Code written by Talant I.D. */ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define OK cout << "OK" << endl; const int mod = 1e9+7; ll mode(ll a) { a %= mod; if (a < 0) a += mod; return a; } ll subt(ll a, ll b) { return mode(mode(a)-mode(b)); } ll add(ll a, ll b) { return mode(mode(a)+mode(b)); } ll mult(ll a, ll b) { return mode(mode(a)*mode(b)); } ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b&1) res = mult(res, a); a = mult(a, a); b >>= 1; } return res; } int main() { do_not_disturb int n, a, b; cin >> n >> a >> b; vector <ll> v(n+1), pref(n+1); for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= n; i++) pref[i] = pref[i-1]+v[i]; if (n <= 20) { ll ans = 9e18; for (int mask = 0; mask < (1<<n); mask++) { ll prev = 1, j = 1, cnt = 0, sum = 0; while (j <= n) { while (j <= n && !(mask&(1<<(j-1)))) { j++; } if (prev < j) { cnt++; sum |= pref[j-1]-pref[prev-1]; } prev = j; j++; } if (prev == n) { sum |= v[n]; cnt++; } if (a <= cnt && cnt <= b) { ans = min(ans, sum); } } cout << ans; } else if (n <= 50 && a >= 1) { bool dp[53][53][53]; memset(dp, false, sizeof(dp)); dp[0][0][0] = 1; for (int i = 1; i <= n; i++) { dp[i][pref[i]][1] = 1; } for (int par = 2; par <= n; par++) { for (int i = 1; i <= n; i++) { for (int orr = 0; orr <= 50; orr++) { for (int j = i-1; j >= par-1; j--) { dp[i][orr|(pref[i]-pref[j])][par] |= dp[j][orr][par-1]; } } } } int ans = 2e9; for (int par = a; par <= b; par++) { for (int orr = 0; orr <= 50; orr++) { if (dp[n][orr][par]) ans = min(ans, orr); } } cout << ans; } else if (n <= 100 && a == 1) { } else if (n <= 100) { } else { } return 0; }
#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...