Submission #1128576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128576		AverageAmogusEnjoyer	Sails (IOI07_sails)	C++17	70 / 100	1095 ms	1772 KiB

sails

#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 new_placed[N];
int order[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];
  });
  // placed[0] += diff
  //   
  int lh = 0;
  for (int t=0;t<n;t++) {
    int i = order[t];
    int diff = h[i] - lh;
    lh = h[i];
    placed[0] += diff;
    int j = 0;
    new_placed[0] = placed[0];
    for (;k[i]>0;j++) {
      int now = min(k[i],placed[j]);
      new_placed[j + 1] = placed[j + 1] + now;
      k[i] -= now;
      new_placed[j] -= now;
    }
    for (int z=0;z<=j;z++) 
      placed[z] = new_placed[z];
    // for (int z=0;z<=10;z++)
      // cout << placed[z] << " ";
    // cout << endl;
  }

  ll ans = 0;
  for (int i=0;i<N;i++) {
    ans += 1LL * i * (i - 1) / 2 * placed[i];
  }
  cout << ans << endl;
} 

• 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: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10