oj.uz

Submission #895050

# Submission time Handle Problem Language Result Execution time Memory
895050 2023-12-29T11:16:39 Z vjudge1 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 67 ms 10884 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 2404 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 11 ms 6748 KB Output is correct
6 Correct 39 ms 6792 KB Output is correct
7 Correct 67 ms 10880 KB Output is correct
8 Correct 53 ms 10876 KB Output is correct
9 Correct 55 ms 10880 KB Output is correct
10 Correct 38 ms 10632 KB Output is correct
11 Correct 65 ms 10884 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 2404 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 9 ms 4700 KB Output is correct
5 Correct 11 ms 6748 KB Output is correct
6 Correct 39 ms 6792 KB Output is correct
7 Correct 67 ms 10880 KB Output is correct
8 Correct 53 ms 10876 KB Output is correct
9 Correct 55 ms 10880 KB Output is correct
10 Correct 38 ms 10632 KB Output is correct
11 Correct 65 ms 10884 KB Output is correct
12 Incorrect 27 ms 6796 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 2404 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 2404 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 2404 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 -