oj.uz

Submission #844907

# Submission time Handle Problem Language Result Execution time Memory
844907 2023-09-06T08:25:31 Z nskybytskyi Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 179 ms 27332 KB 
#include <bits/stdc++.h>
using namespace std;

// dp[i][j] = min cost to get a[k] >= b[k] for all k <= i
// and (sum (a[k] - b[k]) over k <= i) <= j
// f_i(j) := dp[i][j] is decreasing and convex in j

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n;
  cin >> n;

  vector<pair<int, int>> ab(n);
  for (auto& [a, b] : ab) {
    cin >> a >> b;
  }

  vector<int> differences(n);
  for (int i = 0; i < n; ++i) {
    const auto& [a, b] = ab[i];
    differences[i] = a - b;
  }

  vector<int64_t> prefix_sums(n + 1);
  for (int i = 0; i < n; ++i) {
    prefix_sums[i + 1] = prefix_sums[i] + differences[i];
  }

  // looking for a non-decreasing sequence of prefix sums
  // with smallest possible sum of absolute differences
  // same problem but cannot modify prefix_sums[0]=0 and prefix_sums[n]
  // same as saying there are infinitely many breakpoints at 0

  int64_t value{0};
  priority_queue<int64_t> slope;

  for (int i = 1; i < n; ++i) {
    slope.push(prefix_sums[i]);
    slope.push(prefix_sums[i]);
    value += max<int64_t>(0, slope.top()) - prefix_sums[i];
    if (slope.top() > 0) {
      slope.pop();
    }
  }

  while (!slope.empty()) {
    value += max<int64_t>(0, slope.top() - prefix_sums[n]);
    slope.pop();
  }

  cout << value << '\n';
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 14 ms 2268 KB Output is correct
5 Correct 29 ms 4048 KB Output is correct
6 Correct 80 ms 10748 KB Output is correct
7 Correct 176 ms 27332 KB Output is correct
8 Correct 142 ms 21096 KB Output is correct
9 Correct 167 ms 22724 KB Output is correct
10 Correct 90 ms 16584 KB Output is correct
11 Correct 96 ms 18124 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 14 ms 2268 KB Output is correct
5 Correct 29 ms 4048 KB Output is correct
6 Correct 80 ms 10748 KB Output is correct
7 Correct 176 ms 27332 KB Output is correct
8 Correct 142 ms 21096 KB Output is correct
9 Correct 167 ms 22724 KB Output is correct
10 Correct 90 ms 16584 KB Output is correct
11 Correct 96 ms 18124 KB Output is correct
12 Correct 41 ms 6768 KB Output is correct
13 Correct 106 ms 14848 KB Output is correct
14 Correct 179 ms 26996 KB Output is correct
15 Correct 152 ms 19704 KB Output is correct
16 Correct 161 ms 19400 KB Output is correct
17 Correct 86 ms 20420 KB Output is correct
18 Correct 1 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 528 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 2 ms 856 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 14 ms 2268 KB Output is correct
12 Correct 29 ms 4048 KB Output is correct
13 Correct 80 ms 10748 KB Output is correct
14 Correct 176 ms 27332 KB Output is correct
15 Correct 142 ms 21096 KB Output is correct
16 Correct 167 ms 22724 KB Output is correct
17 Correct 90 ms 16584 KB Output is correct
18 Correct 96 ms 18124 KB Output is correct
19 Correct 41 ms 6768 KB Output is correct
20 Correct 106 ms 14848 KB Output is correct
21 Correct 179 ms 26996 KB Output is correct
22 Correct 152 ms 19704 KB Output is correct
23 Correct 161 ms 19400 KB Output is correct
24 Correct 86 ms 20420 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 1 ms 528 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 2 ms 600 KB Output is correct
29 Correct 2 ms 600 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 2 ms 856 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 38 ms 5588 KB Output is correct
34 Correct 93 ms 15816 KB Output is correct
35 Correct 163 ms 22984 KB Output is correct
36 Correct 159 ms 20680 KB Output is correct
37 Correct 144 ms 21192 KB Output is correct
38 Correct 159 ms 22728 KB Output is correct
39 Correct 106 ms 18484 KB Output is correct
40 Correct 119 ms 17096 KB Output is correct
41 Correct 92 ms 17364 KB Output is correct
42 Correct 92 ms 18052 KB Output is correct
43 Correct 91 ms 18120 KB Output is correct
44 Correct 93 ms 17268 KB Output is correct
45 Correct 172 ms 22216 KB Output is correct
46 Correct 118 ms 18376 KB Output is correct
47 Correct 105 ms 15564 KB Output is correct