Submission #64266

#TimeUsernameProblemLanguageResultExecution timeMemory
64266kingpig9Bali Sculptures (APIO15_sculpture)C++11
100 / 100
123 ms2468 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2018; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) int N, A, B; ll P[MAXN]; int dp[MAXN]; bitset<MAXN> msk[MAXN]; bool can (ll cur, int pos, ll s) { return (s ^ (s & cur)) < (1ll << pos); } bool moo (ll cur, int pos) { //try NOT to add pos. //But at the same time, keep the leading bits. //is it possible to do it in this amount? if (A == 1) { //need N^2, not N^3 / 32. dp[0] = 0; for (int i = 1; i <= N; i++) { dp[i] = MAXN; for (int j = 0; j < i; j++) { ll s = P[i] - P[j]; //s, cur, pos are what matter. //whatever s has and cur does not have. //110101........ (cur) // p // c c c //"c"s indicate the bits that can't be set //note that c is also at the first dot. if (can(cur, pos, s)) { dp[i] = min(dp[i], dp[j] + 1); } } } return dp[N] <= B; } else { msk[0][0] = 1; for (int i = 1; i <= N; i++) { msk[i].reset(); for (int j = 0; j < i; j++) { ll s = P[i] - P[j]; if (can(cur, pos, s)) { msk[i] |= (msk[j] << 1); } } } for (int i = A; i <= B; i++) { if (msk[N][i]) { return true; } } return false; } } int main() { scanf("%d %d %d", &N, &A, &B); for (int i = 1; i <= N; i++) { scanf("%lld", &P[i]); P[i] += P[i - 1]; } ll ans = 0; for (int i = 42; i >= 0; i--) { if (!moo(ans, i)) { ans ^= (1ll << i); } } printf("%lld\n", ans); }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &P[i]);
   ~~~~~^~~~~~~~~~~~~~~
#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...