Submission #402798

#TimeUsernameProblemLanguageResultExecution timeMemory
402798yoavLBali Sculptures (APIO15_sculpture)C++14
9 / 100
34 ms8316 KiB
#include <iostream> #include <vector> #include <algorithm> #define upmax(a, b) a = max(a, b); #define upmin(a, b) a = min(a, b); #define pr(x) cout << x << endl; using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; const ll inf = 1e18; const ll maxn = 1026; // each one is smaller than 10. so sum is no more than 500. Which means maxn's last bit is no more than 1023. const ll maxg = 20; ll n, a, b; vll arr; ll ans; vll s; void brute(vll& div, ll ind) { if (ind == n) { if (div.size() < a-1 || div.size() > b-1) return; ll res = 0; ll cursum = 0; ll p = 0; for (ll i = 0; i < n; i++) { cursum += arr[i]; if (p < div.size() && div[p] == i) { res |= cursum; p++; cursum = 0; } } res |= cursum; upmin(ans, res); return; } div.push_back(ind); if(ind < n-1) brute(div, ind + 1); div.pop_back(); brute(div, ind + 1); } ll sum(ll l, ll r) { ll res = s[r]; if (l) res -= s[l - 1]; return res; } ll calc_dp() { /* dp[i][j][k] = is it possible to use first i vals to form j groups with OR-SUM equals k. */ vvvll dp(n+1, vvll(maxg + 1, vll(maxn, false))); dp[0][0][0] = true; for (ll i = 0; i <= n; i++) { for (ll j = 0; j <= maxg; j++) { for (ll k = 0; k < maxn; k++) { if (!dp[i][j][k]) continue; ll cursum = 0; for (ll m = i + 1; m <= n; m++) { cursum += arr[m - 1]; if (cursum >= maxn) while (true); dp[m][j + 1][k | cursum] = 1; } } } } ll res = inf; for (ll j = a; j <= b; j++) { for (ll k = 0; k < maxn; k++) { if (dp[n][j][k]) upmin(res, k); } } return res; } int main() { cin >> n >> a >> b; arr.resize(n); for (ll i = 0; i < n; i++) cin >> arr[i]; s.resize(n); s[0] = arr[0]; for (ll i = 1; i < n; i++) s[i] = arr[i] + s[i - 1]; ans = inf; if (n <= 20) { vll div; brute(div, 0); pr(ans); return 0; } ans = calc_dp(); pr(ans); } /* 6 1 3 8 1 2 1 5 4 */

Compilation message (stderr)

sculpture.cpp: In function 'void brute(vll&, ll)':
sculpture.cpp:26:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   26 |   if (div.size() < a-1 || div.size() > b-1) return;
      |       ~~~~~~~~~~~^~~~~
sculpture.cpp:26:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   26 |   if (div.size() < a-1 || div.size() > b-1) return;
      |                           ~~~~~~~~~~~^~~~~
sculpture.cpp:32:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    if (p < div.size() && div[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...