oj.uz

Submission #172697

# Submission time Handle Problem Language Result Execution time Memory
172697 2020-01-02T12:16:08 Z AlexLuchianov Sails (IOI07_sails) C++14
100 / 100
 135 ms 4348 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
ll v[1 + nmax];

struct Level{
  ll val;
  ll scount;
  bool operator < (Level const &a) const{
    return val > a.val;
  }
};

ll f(int x){
  return 1LL * (x - 1) * x / 2;
}

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++){
    int h, l;
    cin >> h >> l;
    v[h + 1]--;
    v[h - l + 1]++;
  }
  for(int i = 1;i <= nmax; i++)
    v[i] += v[i - 1];
  priority_queue<Level> pq;
  pq.push({nmax + 2, 0});
  pq.push({nmax + 1, 0});
  for(int i = 1;i <= nmax; i++){
    ll money = v[i];
    pq.push({0, 1});
    while(0 < money){
      Level curr = pq.top();
      pq.pop();
      Level prev = pq.top();
      pq.pop();
      if(curr.val == prev.val){
        pq.push({curr.val, curr.scount + prev.scount});
        continue;
      } else {
        if(curr.scount * (prev.val - curr.val) <= money){
          pq.push({prev.val, curr.scount});
          money -= curr.scount * (prev.val - curr.val);
          pq.push(prev);
        } else {
          int addall = money / curr.scount, addone = money % curr.scount;
          money = 0;
          if(0 <  curr.scount - addone)
            pq.push({curr.val + addall, curr.scount - addone});
          if(0 < addone)
            pq.push({curr.val + addall + 1, addone});
          pq.push(prev);
        }
      }
    }
  }
  ll result = 0;
  while(0 < pq.size()){
    result += f(pq.top().val) * pq.top().scount;
    pq.pop();
  }
  cout << result;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3564 KB Output is correct
2 Correct 18 ms 3308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3308 KB Output is correct
2 Correct 18 ms 3304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3308 KB Output is correct
2 Correct 19 ms 3180 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3308 KB Output is correct
2 Correct 17 ms 3308 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3308 KB Output is correct
2 Correct 61 ms 1528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3304 KB Output is correct
2 Correct 44 ms 3544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3688 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 2168 KB Output is correct
2 Correct 119 ms 2704 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4348 KB Output is correct
2 Correct 97 ms 3948 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 2952 KB Output is correct
2 Correct 115 ms 4332 KB Output is correct