Submission #249158

#TimeUsernameProblemLanguageResultExecution timeMemory
249158rdd6584Bali Sculptures (APIO15_sculpture)C++14
100 / 100
198 ms512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, a, b; int vec[2000]; int dist[2000]; int dp[100][101]; ll fil; int go(int o, int k) { if (o == n) return a <= k && k <= b; if (dp[o][k] != -1) return dp[o][k]; int ret = 0; ll sum = 0; for (int i = o; i < n; i++) { sum += vec[i]; if (sum & (fil)); else ret = max(ret, go(i+1, k+1)); } return dp[o][k] = ret; } int miv(int o) { if (o == n) return 0; if (dist[o] != -1) return dist[o]; int ret = 1e9; ll sum = 0; for (int i = o; i < n; i++) { sum += vec[i]; if (sum & fil); else ret = min(ret, miv(i+1)); } return dist[o] = ret + 1; } int main() { scanf("%d %d %d", &n ,&a, &b); for (int i = 0; i < n; i++) scanf("%d", &vec[i]); // 이 비트를 끌 수 있는 지? // 그게 아닌 경우는... 켜도 된다. for (int i = 50; i >= 0; i--) { ll tmp = fil; fil = tmp|(1LL<<i); if (a == 1) { memset(dist, -1, sizeof(dist)); int k = miv(0); if (k <= b) tmp = fil; } else { memset(dp, -1, sizeof(dp)); int k = go(0,0); if (k) tmp = fil; } fil = tmp; } ll ret = 0; for (int i = 50; i >= 0; i--) { if (fil & (1LL<<i)); else ret |= 1LL<<i; } printf("%lld", ret); }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:41:10: 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:42:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%d", &vec[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...