Submission #232918

#TimeUsernameProblemLanguageResultExecution timeMemory
232918andreiomdBali Sculptures (APIO15_sculpture)C++11
100 / 100
453 ms512 KiB
#include <iostream> using namespace std; const int NMAX = 2e3 + 5, INF = 1e9; int N, A, B, Y[NMAX]; long long sp[NMAX], BitMask; static inline void Read () { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cin >> N >> A >> B; for(int i = 1; i <= N; ++i) cin >> Y[i], sp[i] = sp[i - 1] + 1LL * Y[i]; return; } auto Check = [] (int byte, long long Sum) { if(Sum & (1LL << byte)) return 0; Sum >>= (1LL * (byte + 1)); if((Sum | BitMask) != BitMask) return 0; return 1; }; static inline bool Ok_1 (int byte) { bool dp[N + 1][N + 1]; for(int i = 0; i <= N; ++i) for(int j = 0; j <= N; ++j) dp[i][j] = 0; dp[0][0] = 1; for(int i = 1; i <= N; ++i) for(int j = 1; j <= i; ++j) for(int k = 0; k < i && !dp[i][j]; ++k) if(dp[k][j - 1] && Check(byte, sp[i] - sp[k])) dp[i][j] = 1; for(int i = A; i <= B; ++i) if(dp[N][i]) return 1; return 0; } static inline bool Ok_2 (int byte) { int dp[N + 5]; dp[0] = 0; for(int i = 1; i <= N; ++i) { dp[i] = INF; for(int j = 0; j < i; ++j) if(Check(byte, sp[i] - sp[j])) dp[i] = min(dp[i], dp[j] + 1); } return (dp[N] <= B); } auto Ok = [] (int byte) { if(N <= 1e2) return Ok_1(byte); return Ok_2(byte); }; static inline void Solve () { long long ans = 0; for(int i = 40; i >= 0; --i) { bool Now = Ok(i); BitMask = (BitMask << 1LL); if(Now) continue; else ans += 1LL * (1LL << i), ++BitMask; } cout << ans << '\n'; return; } int main() { Read(); Solve(); return 0; }
#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...