Submission #172697

#	Time	Username	Problem	Language	Result	Execution time	Memory
172697		AlexLuchianov	Sails (IOI07_sails)	C++14	100 / 100	135 ms	4348 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10