Submission #962573

#TimeUsernameProblemLanguageResultExecution timeMemory
962573BhavayGoyalBali Sculptures (APIO15_sculpture)C++14
100 / 100
132 ms604 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ld long double #define ar array #define vi vector<int> #define vii vector<vector<int>> #define pii pair<int, int> #define pb push_back #define all(x) x.begin(), x.end() #define f first #define s second #define endl "\n" const int MOD = 1e9+7; const int inf = 1e9; const int linf = 1e18; const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1}; const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // -------------------------------------------------- Main Code -------------------------------------------------- void sol() { int n, a, b; cin >> n >> a >> b; int arr[n+1]; for (int i = 1; i <= n; i++) cin >> arr[i]; if (a != 1) { int dp[n+1][n+1]; int pref = 0; for (int k = 60; k >= 0; k--) { for (int i = 0; i <= n; i++) { for (int left = 0; left <= n; left++) { if (i == 0 && left == 0) {dp[i][left] = 0; continue;} if (i == 0 || left == 0) {dp[i][left] = inf; continue;} dp[i][left] = inf; int sum = 0; for (int j = i; j >= 1; j--) { sum += arr[j]; if (((pref>>k)|(sum>>k)) == (pref>>k)) dp[i][left] = min(dp[i][left], dp[j-1][left-1]+1); } } } int mn = inf; for (int i = a; i <= b; i++) mn = min(mn, dp[n][i]); if (mn > b) pref |= (1ll<<k); } cout << pref << endl; } else { int pref = 0; for (int k = 60; k >= 0; k--) { int dpp[n+1]; dpp[0] = 0; for (int i = 1; i <= n; i++) { int sum = 0; dpp[i] = inf; for (int j = i; j >= 1; j--) { sum += arr[j]; if (((pref>>k)|(sum>>k)) == (pref>>k)) dpp[i] = min(dpp[j-1]+1, dpp[i]); } } if (dpp[n] > b) pref |= (1ll<<k); } cout << pref << endl; } } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { sol(); } 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...