Submission #1101099

#TimeUsernameProblemLanguageResultExecution timeMemory
1101099Zero_OPBali Sculptures (APIO15_sculpture)C++14
100 / 100
95 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i) #define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i) #define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i) #define all(v) begin(v), end(v) #define compact(v) v.erase(unique(all(v)), end(v)) #define sz(v) (int)v.size() #define dbg(x) "[" #x " = " << (x) << "]" template<typename T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } using ll = long long; using ld = long double; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); } template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); } const int MAX = 2e3 + 5; int n, A, B, a[MAX]; ll pref[MAX]; ll sum(int l, int r){ return pref[r] - pref[l - 1]; } namespace subtask4{ bool dp[105][105]; void solve(){ ll ans = (1LL << 60) - 1; for(int bit = 59; bit >= 0; --bit){ ans ^= (1LL << bit); //try to erase largest bit memset(dp, false, sizeof(dp)); dp[0][0] = true; for(int s = 1; s <= B; ++s){ for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ if((sum(j, i) | ans) == ans){ dp[s][i] |= dp[s - 1][j - 1]; } } } } bool ok = false; for(int s = A; s <= B; ++s){ ok |= dp[s][n]; } if(!ok) ans ^= (1LL << bit); //cant } cout << ans << '\n'; } } namespace subtask5{ int dp[MAX]; void solve(){ ll ans = (1LL << 60) - 1; for(int bit = 59; bit >= 0; --bit){ ans ^= (1LL << bit); //try to erase largest bit memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ if((sum(j, i)| ans) == ans){ dp[i] = min(dp[i], dp[j - 1] + 1); } } } if(dp[n] > B) ans ^= (1LL << bit); //cant } cout << ans << '\n'; } } void testcase(){ cin >> n >> A >> B; FOR(i, 1, n) cin >> a[i], pref[i] = pref[i - 1] + a[i]; if(n <= 100) subtask4::solve(); else subtask5::solve(); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #define filename "task" if(fopen(filename".inp", "r")){ freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); } int T = 1; //cin >> T; while(T--) testcase(); return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'bool minimize(T&, const T&)':
sculpture.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
sculpture.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
sculpture.cpp: In function 'bool maximize(T&, const T&)':
sculpture.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if(a < b) return a = b, true; return false;
      |     ^~
sculpture.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(filename".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(filename".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...