Submission #223695

#	Time	Username	Problem	Language	Result	Execution time	Memory
223695		FieryPhoenix	Sails (IOI07_sails)	C++11	40 / 100	1096 ms	2284 KiB

sails

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,H[100001],K[100001];
int cnt[100001];

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N;
  vector<pair<int,int>>v;
  for (int i=0;i<N;i++){
    cin>>H[i]>>K[i];
    v.push_back({H[i],K[i]});
  }
  sort(v.begin(),v.end());
  for (int i=0;i<N;i++){
    /*
    cout<<"SAIL "<<i<<": "<<v[i].first<<' '<<v[i].second<<endl;
    for (int i=0;i<=10;i++)
      cout<<cnt[i]<<' ';
    cout<<endl;
    */
    int pre=0;
    if (i>0) pre=v[i-1].first;
    cnt[0]+=v[i].first-pre;
    int k=v[i].second;
    deque<pair<int,int>>did;
    for (int j=0;;j++){
      if (cnt[j]>=k){
	did.push_front({j,k});
	k=0;
	break;
      }
      else{
	did.push_front({j,cnt[j]});
	k-=cnt[j];
      }
    }
    for (auto it:did){
      cnt[it.first]-=it.second;
      cnt[it.first+1]+=it.second;
    }
  }
  ll ans=0;
  for (ll i=1;i<=100000;i++){
    ll num=cnt[i];
    ans+=num*(i*(i-1))/2;
  }
  cout<<ans<<endl;
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10