Submission #882912

#TimeUsernameProblemLanguageResultExecution timeMemory
882912Onur_IlgazBali Sculptures (APIO15_sculpture)C++17
100 / 100
113 ms604 KiB
#include <bits/stdc++.h> #define fast cin.tie(0)->sync_with_stdio(0); #define int long long #define inf ((int)1e18) using namespace std; vector <int> arr(2001), pref(2001); bool solve(int val, int n, int a, int b) { vector<int> dp(n + 1, inf); dp[0] = 0; for(int i = 1; i <= n; i++) { for(int from = 0; from < i; from++) { if(((pref[i] - pref[from]) & val) == 0) { dp[i] = min(dp[i], dp[from] + 1); // dp[i] = i'ye kadar min kaç bölmelendirmeyle value'ya ulaşılabilinir } } } return (dp[n] <= b); } bool solve2(int val, int n, int a, int b) { vector<vector<bool> > dp(n + 1, vector<bool>(n + 1)); dp[0][0] = 1; for(int i = 1; i <= n; i++) { for(int cnt = 1; cnt <= b; cnt++){ for(int from = 0; from < i; from++) { if(dp[from][cnt-1] && (((pref[i] - pref[from]) & val) == 0)) { dp[i][cnt] = 1; } } } } for(int i = a; i <= b; i++) { if(dp[n][i] == 1) return 1; } return 0; } int32_t main(){ fast int n, a, b; cin >> n >> a >> b; for(int i = 1; i <= n; i++) { cin >> arr[i]; pref[i] = pref[i-1] + arr[i]; } int val = 0; for(int bit = (1ll << 60ll); bit > 0; bit /= 2) { bool ans; if(n > 100) ans = solve(val + bit, n, a, b); else ans = solve2(val + bit, n, a, b); val += ans * bit; } cout << (((1ll << 61ll) - 1) ^ val) << "\n"; }
#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...