Submission #886835

#TimeUsernameProblemLanguageResultExecution timeMemory
886835anha3k25cvpBali Sculptures (APIO15_sculpture)C++14
100 / 100
373 ms16472 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 1 + 2e3; const int inf = 7 + 1e9; int main() { #define TASKNAME "code" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen (TASKNAME".inp", "r", stdin); freopen (TASKNAME".out", "w", stdout); } int n, L, R; cin >> n >> L >> R; vector <ll> a(n + 1, 0); for (int i = 1; i <= n; i ++) { cin >> a[i]; a[i] += a[i - 1]; } ll ans = 0; vector <int> ok(41, 0); vector <vector <int>> OK(n + 1, vector <int> (n + 1, 1)); int ma = 42; while (1) { int lo = 0, hi = ma; while (lo < hi) { int mid = (lo + hi) / 2, bit = mid - 1; vector <int> mi(n + 1, inf), ma(n + 1, 0); mi[0] = 0; ma[0] = 0; for (int j = 0; j <= n; j ++) if (mi[j] <= R) for (int i = j + 1; i <= n; i ++) { if (!OK[j][i]) continue; ll val = a[i] - a[j]; int check = 1; for (int pos = bit + 1; pos < 41; pos ++) if (((val >> pos) & 1) && !ok[pos]) { check = 0; break; } if (!check) continue; mi[i] = min(mi[i], mi[j] + 1); ma[i] = max(ma[i], ma[j] + 1); } if (mi[n] <= R && ma[n] >= L) hi = mid; else lo = mid + 1; } int bit = lo - 1; if (bit < 0) { cout << ans; return 0; } for (int i = 1; i <= n; i ++) for (int j = 0; j < i; j ++) { if (!OK[j][i]) continue; ll val = a[i] - a[j]; int check = 1; for (int pos = bit + 1; pos < 41; pos ++) if (((val >> pos) & 1) && !ok[pos]) OK[j][i] = 0; } ma = bit; ok[bit] = 1; ans += (ll)1 << bit; } return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:72:21: warning: unused variable 'check' [-Wunused-variable]
   72 |                 int check = 1;
      |                     ^~~~~
sculpture.cpp:19:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:20:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen (TASKNAME".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...