Submission #41492

#TimeUsernameProblemLanguageResultExecution timeMemory
41492cmasterBali Sculptures (APIO15_sculpture)C++14
100 / 100
236 ms748 KiB
#include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/detail/standard_policies.hpp>*/ #define pb push_back #define mp make_pair #define sz(s) ((int)(s.size())) #define all(s) s.begin(), s.end() #define rep(i, a, n) for (int i = a; i <= n; ++i) #define per(i, n, a) for (int i = n; i >= a; --i) #define onlycin ios_base::sync_with_stdio(false); cin.tie(0) #define F first #define S second using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; /*typedef tree< pair < int, int >, null_type, less< pair < int, int > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;*/ // find_by_order() order_of_key() const int MAXN = (int)5e5+228; const char nxtl = '\n'; const int mod = (int)1e9+7; const double eps = (double)1e-7; template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} int n, l, r, a[MAXN]; int dp[MAXN], dp2[MAXN]; inline bool check(const ll &lim, const ll &mid, const ll &MOD, const ll &tmp) { dp[0] = 0; dp2[0] = 0; rep(i, 1, n) { ll cur = 0ll; dp[i] = n+n; dp2[i] = -(n+n); per(j, i, 1) { cur += a[j]; if(cur >= lim) break; if((cur & tmp) == 0ll && cur % MOD < mid) { updmin(dp[i], dp[j-1]+1); updmax(dp2[i], dp2[j-1]+1); } } } return dp[n] <= r && dp2[n] >= l; } int main() { #ifdef accepted freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif onlycin; cin >> n >> l >> r; rep(i, 1, n) cin >> a[i]; int last = 42, fr = 42; ll res = 0ll; ll just = 0ll; per(bit, 40, 0) { ll lim = (1ll << fr*1ll); if(last == 42) lim = (1ll << bit); if(!check(lim, (1ll<<bit*1ll), (1ll << last*1ll), just)) { if(fr == 42) fr = bit+1; res |= (1ll << bit*1ll); last = bit; } else just |= (1ll << bit*1ll); } cout << res << nxtl; 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...