Submission #886242

#TimeUsernameProblemLanguageResultExecution timeMemory
886242tsumondaiBali Sculptures (APIO15_sculpture)C++14
100 / 100
126 ms2684 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define Task "APIO15_sculpture" #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 2000 + 5; const int oo = 1e9, mod = 1e9 + 7; int n, l, r; int pref[N]; bool dp[N][N]; int dp1[N]; int sum(int a, int b) { return pref[b] - pref[a - 1]; } bool check(int val) { dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int cnt = 1; cnt <= i; cnt++) { dp[i][cnt] = 0; for (int j = 0; j < i; j++) { if (dp[j][cnt - 1] && ((val & sum(j + 1, i)) == 0) ) dp[i][cnt] = 1; } } } bool ret = 0; for (int i = l; i <= r; i++) { ret |= dp[n][i]; } return ret; } bool check1(int val) { dp1[0] = 0; for (int i = 1; i <= n; i++) { dp1[i] = n + 1; for (int j = 0; j < i; j++) { if ((sum(j + 1, i) & val) == 0) dp1[i] = min(dp1[i], dp1[j] + 1); } } return (dp1[n] <= r); } void process() { cin >> n >> l >> r; for (int i = 1; i <= n; i++) { cin >> pref[i]; pref[i] += pref[i - 1]; } if (l != 1) { int cur = 0; for (int pw = 62; pw >= 0; pw--) { if (check(cur + (1ll << pw))) cur += (1ll << pw); } cout << LLONG_MAX - cur << endl; } else { int cur = 0; for (int pw = 62; pw >= 0; pw--) { if (check1(cur + (1ll << pw))) cur += (1ll << pw); } cout << LLONG_MAX - cur << endl; } } signed main() { cin.tie(0)->sync_with_stdio(false); if (fopen(Task".INP", "r")) { freopen(Task".INP", "r", stdin); freopen(Task".OUT", "w", stdout); } process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } // dont stop

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:88:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...