oj.uz

Submission #634765

# Submission time Handle Problem Language Result Execution time Memory
634765 2022-08-24T21:31:24 Z null_awe Uplifting Excursion (BOI22_vault) C++14
0 / 100
 1 ms 212 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long

int main() {
  int n; cin >> n; n = 2 * n + 1;
  ll l; cin >> l;
  vector<ll> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];
  if (l < 0) reverse(arr.begin(), arr.end()), l = -l;
  for (int i = 0; i < n / 2; ++i) arr[n - 1 - i] += arr[i], l += (n / 2 - i) * arr[i], arr[i] = 0;
  ll sum = 0;
  vector<ll> count(n / 2 + 1); count[0] = arr[n / 2];
  for (int i = 1; i <= n / 2; ++i) {
    if (sum == l) break;
    if (arr[i + n / 2] * i + sum <= l) sum += arr[i + n / 2] * i, swap(count[i], arr[i + n / 2]);
    else {
      int take = (l - sum) / i;
      sum += i * take, count[i] += take, arr[i + n / 2] -= take;
      //cout << sum << '\n';
      int sum2 = 0;
      vector<ll> copy = count, copy2 = arr;
      for (int j = i; j > 0; --j) {
        while (count[j]) {
          if (sum2 >= i + sum - l) break;
          --count[j], ++arr[j + n / 2], sum2 += j;
        }
        if (count[j]) break;
      }
      if (sum + i - sum2 > l) {
        count = copy, arr = copy2;
        continue;
      }
      sum += i - sum2;
      ++count[i], --arr[i + n / 2];
    }
    //cout << sum << '\n';
  }
  if (sum != l) cout << "impossible\n";
  else {
    ll ans = 0;
    for (ll num : count) ans += num;
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -