oj.uz

Submission #895073

# Submission time Handle Problem Language Result Execution time Memory
895073 2023-12-29T11:36:13 Z d4xn Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 177 ms 22612 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N = 1e6+6;
 
int n, a[N], b[N];
set<int> st;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    if (a[i] > b[i]) st.insert(i);
  }
  st.insert(-1);
  st.insert(n);

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] >= b[i]) continue;

    while (a[i] < b[i]) {
      auto l = prev(st.lower_bound(i));
      auto r = st.lower_bound(i);

      int x = *l;
      int y = *r;
      
      int d1 = abs(x - i);
      int d2 = abs(y - i);

      if (x!=-1){//y == n || (x != -1 && d1 <= d2)) {
        int z = a[x]-b[x];
        int z2 = b[i]-a[i];
        int z3 = min(z, z2);

        a[i] += z3;
        a[x] -= z3;
        ans += z3*d1;

        if (a[x] == b[x]) st.erase(x);
      }
      else {
        int z = a[y]-b[y];
        int z2 = b[i]-a[i];
        int z3 = min(z, z2);

        a[i] += z3;
        a[y] -= z3;
        ans += z3*d2;

        if (a[y] == b[y]) st.erase(y);
      }
    }
  }
  cout << ans << "\n";
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 13 ms 5724 KB Output is correct
5 Correct 26 ms 9052 KB Output is correct
6 Correct 49 ms 8968 KB Output is correct
7 Correct 177 ms 22612 KB Output is correct
8 Correct 128 ms 22608 KB Output is correct
9 Correct 149 ms 22424 KB Output is correct
10 Correct 127 ms 22380 KB Output is correct
11 Correct 121 ms 22604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 13 ms 5724 KB Output is correct
5 Correct 26 ms 9052 KB Output is correct
6 Correct 49 ms 8968 KB Output is correct
7 Correct 177 ms 22612 KB Output is correct
8 Correct 128 ms 22608 KB Output is correct
9 Correct 149 ms 22424 KB Output is correct
10 Correct 127 ms 22380 KB Output is correct
11 Correct 121 ms 22604 KB Output is correct
12 Incorrect 32 ms 8904 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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