Submission #725324

#	Time	Username	Problem	Language	Result	Execution time	Memory
725324		quiet_space	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	83 ms	340 KiB

sculpture

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
int n, l, r; ll s[2005];
namespace code1 {
  const int maxn = 105;
  std::bitset <maxn> b[maxn];
  inline void solve (void) {
    ll ans = (1ll << 41) - 1;
    ROF(bit,40,0) {
      ans ^= 1ll << bit; b[0].set (0);
      FOR(i,1,n) FOR(j,0,i-1) if((s[i] - s[j] | ans) == ans) b[i] |= b[j] << 1;
      if(!b[n].test(l) && b[n]._Find_next(l) > r) ans ^= 1ll << bit;
      FOR(i,0,n) b[i].reset();
    }
    printf("%lld\n", ans);
  }
}
namespace code2 {
  const int maxn = 2005;
  int f[maxn];
  inline void solve (void) {
    ll ans = (1ll << 41) - 1;
    ROF(bit,40,0) {
      std::fill (f, f+n+1, 1<<30); ans ^= 1ll << bit; f[0] = 0;
      FOR(i,1,n) FOR(j,0,i-1) if((s[i] - s[j] | ans) == ans) f[i] = std::min(f[i], f[j] + 1);
      if(f[n] > r) ans ^= 1ll << bit;
    }
    printf("%lld\n", ans);
  }
}
int main (void) {
  n = read(); l = read(); r = read();
  FOR(i,1,n) s[i] = s[i-1] + read();
  if(n <= 100) code1::solve ();
  else code2::solve ();
  return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'void code1::solve()':
sculpture.cpp:19:40: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   19 |       FOR(i,1,n) FOR(j,0,i-1) if((s[i] - s[j] | ans) == ans) b[i] |= b[j] << 1;
      |                                   ~~~~~^~~~~~
sculpture.cpp:20:46: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |       if(!b[n].test(l) && b[n]._Find_next(l) > r) ans ^= 1ll << bit;
      |                           ~~~~~~~~~~~~~~~~~~~^~~
sculpture.cpp: In function 'void code2::solve()':
sculpture.cpp:33:40: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   33 |       FOR(i,1,n) FOR(j,0,i-1) if((s[i] - s[j] | ans) == ans) f[i] = std::min(f[i], f[j] + 1);
      |                                   ~~~~~^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29