Submission #1262545

#TimeUsernameProblemLanguageResultExecution timeMemory
1262545VKhangBali Sculptures (APIO15_sculpture)C++20
100 / 100
65 ms500 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; const long long L = 1e18; #define ll long long #define int long long #define fi first #define se second #define yes {cout << "YES";return;} #define no {cout << "NO"; return;} #define pb push_back #define MASK(i) (1ll << (i)) #define BIT(i, s) ((1ll << (i)) & (s)) #define all(a) a.begin(), a.end() int n, a, b; int c[N]; namespace subtask1{ bool check(){ if (n <= 100) return true; return false; } ll f[N]; bool dp[105][105]; void solve(){ for (int i = 1; i <= n; i++){ f[i] = c[i] + f[i - 1]; } ll mask = 0; for (int k = 41; k >= 0; k--){ memset(dp, false, sizeof dp); dp[0][0] = true; for (int i = 1; i <= n; i++){ for (int j = i; j >= 1; j--){ if (((f[i] - f[j - 1]) & (mask + MASK(k) - 1)) == (f[i] - f[j - 1])){ for (int p = 1; p <= n; p++){ dp[i][p] |= dp[j - 1][p - 1]; } } } } bool ok = true; for (int i = a; i <= b; i++){ if (dp[n][i]) ok = false; } if (ok) mask |= MASK(k); } cout << mask; } } namespace subtask2{ bool check(){ if (n <= 2000) return true; return false; } ll f[N]; int dp[2005]; void solve(){ for (int i = 1; i <= n; i++){ f[i] = c[i] + f[i - 1]; } ll mask = 0; for (int k = 41; k >= 0; k--){ memset(dp, 0x3f, sizeof dp); dp[0] = 0; for (int i = 1; i <= n; i++){ for (int j = i; j >= 1; j--){ if (((f[i] - f[j - 1]) & (mask + MASK(k) - 1)) == (f[i] - f[j - 1])){ dp[i] = min(dp[i], dp[j - 1] + 1); } } } if (dp[n] > b) mask |= MASK(k); } cout << mask; } } void solve() { cin >> n >> a >> b; for (int i = 1; i <= n; i++){ cin >> c[i]; } if (subtask1::check()) return subtask1::solve(); if (subtask2::check()) return subtask2::solve(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); solve(); 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...