Submission #74725

#	Time	Username	Problem	Language	Result	Execution time	Memory
74725		goodbaton	Sails (IOI07_sails)	C++14	100 / 100	42 ms	8448 KiB

sails

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

#define SIZE 100010

int main(){
  int n,h,k,max_h=0;
  ll sum[SIZE] = {};
  priority_queue<pair<ll,ll> > pq;

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%d%d",&h,&k);
    max_h = max(max_h,h);
    
    sum[h]++;
    sum[h-k]--;
  }
  
  for(int i=max_h;i>0;i--){
    sum[i-1] += sum[i];
  }

  for(int i=1;i<=max_h;i++){
    ll v = 1;
    sum[i] *= -1;
    
    while(pq.size() && pq.top().first > sum[i]/v){
      pair<ll,ll> p = pq.top();
      pq.pop();
      sum[i] += p.first * p.second;
      v += p.second;
    }

    sum[i] *= -1;
    
    if(sum[i]%v==0){
      pq.push(make_pair(-(sum[i]/v),v));
    }else{
      pq.push(make_pair(-(sum[i]/v+1),sum[i]%v));
      pq.push(make_pair(-(sum[i]/v),v-sum[i]%v));
    }

  }

  ll ans = 0;

  while(pq.size()){
    pair<ll,ll> p = pq.top();
    pq.pop();

    p.first *= -1;
    ans += p.first*(p.first-1)/2 * p.second;
  }

  printf("%lld\n",ans);

  return 0;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
sails.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&k);
     ~~~~~^~~~~~~~~~~~~~

• 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