Submission #1128569

#TimeUsernameProblemLanguageResultExecution timeMemory
1128569AverageAmogusEnjoyerSails (IOI07_sails)C++17
30 / 100
1096 ms1648 KiB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
  return ui(mrand);
}

const int N=100100;
int n;
int h[N],k[N];
int placed[N];
int order[N];
bool done[N];

int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);
    
  cin >> n;
  for (int i=0;i<n;i++)
    cin >> h[i] >> k[i];
  iota(order,order+n,0);
  sort(order,order+n,[&](int i,int j) {
    return h[i] < h[j];
  });
  for (int t=0;t<n;t++) {
    int i = order[t];
    for (int j=0;j<h[i];j++)
      done[j]=0;
    while(k[i]--) {
      int minp = -1;
      for (int j=0;j<h[i];j++)
        if (!done[j] && (minp==-1 || placed[j] < placed[minp]))
          minp = j;
      done[minp] = 1;
      placed[minp]++;
    }
  }
  ll ans = 0;
  for (int i=0;i<N;i++) {
    ans += 1LL * placed[i] * (placed[i] - 1) / 2;
  }
  cout << ans << endl;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...