Submission #212686

#TimeUsernameProblemLanguageResultExecution timeMemory
212686spdskatrBali Sculptures (APIO15_sculpture)C++14
100 / 100
107 ms540 KiB
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef long long ll; int N, A, B, y[2005], dp[105][105]; int seen[2005], dists[2005]; ll ps[2005]; queue<int> bfs; int solve(ll mask, int bit) { if (N <= 100) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <= N; i++) { for (int k = 1; k <= B; k++) { for (int j = 1; j <= i; j++) { ll val = ps[i] - ps[j-1]; if (((val|mask)^mask) <= ((1LL << bit) - 1)) { dp[i][k] |= dp[j-1][k-1]; } } } } for (int k = A; k <= B; k++) if (dp[N][k]) return 1; return 0; } else { memset(seen, 0, sizeof(seen)); seen[0] = 1; bfs.push(0); while (!bfs.empty()) { int i = bfs.front(); bfs.pop(); if (dists[i] == B) continue; for (int j = i+1; j <= N; j++) { ll val = ps[j] - ps[i]; if (!seen[j] && ((val|mask) ^ mask) <= ((1LL << bit) - 1)) { seen[j] = 1; dists[j] = dists[i] + 1; bfs.push(j); } } } return seen[N]; } } int main() { scanf("%d %d %d", &N, &A, &B); for (int i = 1; i <= N; i++) { scanf("%d", y+i); ps[i] = ps[i-1] + y[i]; } ll res = 0; for (int b = 42; b >= 0; b--) { if (!solve(res, b)) res |= (1LL << b); } printf("%lld\n", res); }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:52: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:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", y+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...