oj.uz

Submission #895048

# Submission time Handle Problem Language Result Execution time Memory
895048 2023-12-29T11:16:28 Z d4xn Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 80 ms 17524 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);
  }

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

      int x = a[r]-b[r];
      int y = b[i]-a[i];
      int z = min(x, y);
      
      a[i] += z;
      a[r] -= z;
      ans += z*(r-i);
    }
  }
  cout << ans << "\n";

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

    auto r = st.upper_bound(i);
    auto l = r;
    if (l != st.begin()) l--;

    vector<int> to_erase;
    while (a[i] < b[i]) {
      int x = *l;
      int y = (r == st.end() ? -1 : *r);

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

      if (x < i && ((r == st.end()) || (a[y] <= b[y]) || (a[x] > b[x] && d1 <= d2))) {
        int z = a[x]-b[x];
        int z2 = b[i]-a[i];

        if (z > z2) {
          a[x] -= z2;
          ans += z2*d1;
          a[i] = b[i];
        }
        else {
          ans += z*d1;
          a[i] += z;
          a[x] = b[x];

          to_erase.push_back(x);
          if (l != st.begin()) l--;
        }
      }
      else {
        int z = a[y]-b[y];
        int z2 = b[i]-a[i];

        if (z > z2) {
          a[y] -= z2;
          ans += z2*d2;
          a[i] = b[i];
        }
        else {
          ans += z*d2;
          a[i] += z;
          a[y] = b[y];
          
          to_erase.push_back(y);
          if (r != st.end()) r++;
        }
      }
    }

    for (int& j : to_erase) st.erase(j);
  }
  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 6 ms 4956 KB Output is correct
5 Correct 12 ms 7260 KB Output is correct
6 Correct 34 ms 9964 KB Output is correct
7 Correct 80 ms 17524 KB Output is correct
8 Correct 54 ms 15744 KB Output is correct
9 Correct 63 ms 15096 KB Output is correct
10 Correct 42 ms 12776 KB Output is correct
11 Correct 42 ms 12660 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 6 ms 4956 KB Output is correct
5 Correct 12 ms 7260 KB Output is correct
6 Correct 34 ms 9964 KB Output is correct
7 Correct 80 ms 17524 KB Output is correct
8 Correct 54 ms 15744 KB Output is correct
9 Correct 63 ms 15096 KB Output is correct
10 Correct 42 ms 12776 KB Output is correct
11 Correct 42 ms 12660 KB Output is correct
12 Incorrect 16 ms 8464 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 2396 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 2396 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 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -