Submission #694131

#TimeUsernameProblemLanguageResultExecution timeMemory
694131finn__Uplifting Excursion (BOI22_vault)C++17
20 / 100
15 ms456 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #pragma GCC target("avx2") int main() { int64_t m, l; cin >> m >> l; vector<int64_t> a(2 * m + 1); for (int64_t &x : a) cin >> x; if (l < 0) { l = -l; for (int64_t i = 0; i < m; i++) swap(a[m - i - 1], a[m + i + 1]); } int64_t p = 0, total_added = 0; vector<int64_t> b(a.begin(), a.end()); for (int64_t i = -m; i <= 0; i++) p += a[i + m] * i, b[i + m] = 0, total_added += a[i + m]; for (int64_t i = 1; i <= m; i++) { for (int64_t j = 62; j >= 0; j--) if (1LL << j <= b[i + m] && p + (1LL << j) * i <= l) { p += (1LL << j) * i; b[i + m] -= 1LL << j; total_added += 1LL << j; } } if (p < l - m) { p = 0; total_added = 0; b = vector<int64_t>(a.begin(), a.end()); for (int64_t i = 0; i <= m; i++) p += a[i + m] * i, b[i + m] = 0, total_added += a[i + m]; for (int64_t i = -1; i >= -m; i--) { for (int64_t j = 62; j >= 0; j--) if (1LL << j <= b[i + m] && p + (1LL << j) * i >= l) { p += (1LL << j) * i; b[i + m] -= 1LL << j; total_added += 1LL << j; } } if (p < l - m) { cout << "impossible\n"; return 0; } } // l resides at m * m. vector<int64_t> dp1(2 * m * m + 1, 0), dp2(2 * m * m + 1, 0); dp1[m * m - (l - p)] = total_added; for (int64_t i = -m; i <= m; i++) { vector<int64_t> max_add(dp1.size(), min<int64_t>(b[i + m], m)), max_remove = vector<int64_t>(dp1.size(), min<int64_t>(a[i + m] - b[i + m], m)); bool f = 1; for (int64_t k = 0; f; k++) { f = 0; for (int64_t j = 0; j < dp1.size(); j++) { if (!dp1[j] || !(0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size() && 1LL << k < max_add[j])) continue; f = 1; dp2[j + (1LL << k) * i] = max<int64_t>(dp2[j + (1LL << k) * i], dp1[j] + (1LL << k)); max_add[j] -= 1LL << k; } swap(dp1, dp2); for (size_t i = 0; i < dp1.size(); i++) dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]); } for (int64_t j = 0; j < dp1.size(); j++) if (dp1[j] && 0 <= j + max_add[j] * i && j + max_add[j] * i < dp1.size()) dp2[j + max_add[j] * i] = max<int64_t>(dp2[j + max_add[j] * i], dp1[j] + max_add[j]); swap(dp1, dp2); for (size_t i = 0; i < dp1.size(); i++) dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]); f = 1; for (int64_t k = 0; f; k++) { f = 0; for (int64_t j = 0; j < dp1.size(); j++) { if (!dp1[j] || !(0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size() && 1LL << k < max_remove[j])) continue; f = 1; dp2[j - (1LL << k) * i] = max<int64_t>(dp2[j - (1LL << k) * i], dp1[j] - (1LL << k)); max_remove[j] -= 1LL << k; } swap(dp1, dp2); for (size_t i = 0; i < dp1.size(); i++) dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]); } for (int64_t j = 0; j < dp1.size(); j++) if (dp1[j] && 0 <= j - max_remove[j] * i && j - max_remove[j] * i < dp1.size()) dp2[j - max_remove[j] * i] = max<int64_t>(dp2[j - max_remove[j] * i], dp1[j] - max_remove[j]); swap(dp1, dp2); for (size_t i = 0; i < dp1.size(); i++) dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]); } if (!dp1[m * m]) cout << "impossible\n"; else cout << dp1[m * m] << '\n'; }

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:77:35: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for (int64_t j = 0; j < dp1.size(); j++)
      |                                 ~~^~~~~~~~~~~~
vault.cpp:79:80: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if (!dp1[j] || !(0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size() && 1LL << k < max_add[j]))
      |                                                             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int64_t j = 0; j < dp1.size(); j++)
      |                             ~~^~~~~~~~~~~~
vault.cpp:92:73: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if (dp1[j] && 0 <= j + max_add[j] * i && j + max_add[j] * i < dp1.size())
      |                                                      ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:104:35: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int64_t j = 0; j < dp1.size(); j++)
      |                                 ~~^~~~~~~~~~~~
vault.cpp:106:80: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 if (!dp1[j] || !(0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size() && 1LL << k < max_remove[j]))
      |                                                             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int64_t j = 0; j < dp1.size(); j++)
      |                             ~~^~~~~~~~~~~~
vault.cpp:119:79: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if (dp1[j] && 0 <= j - max_remove[j] * i && j - max_remove[j] * i < dp1.size())
      |                                                         ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
#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...
#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...