提出 #75892037

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll=pair<ll,ll>;
ll tc,a[1010101],b[1010101],c[1010101],n;
void solve() {
 cin >> n;
 for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
 vector<pll> pq;
 ll zz=0;
 for(int i=1;i<=n;i++) {
  zz+=b[i];
  pq.push_back({zz+c[i],i});
 }
 pq.push_back({1e18,1557888484});
 sort(pq.begin(),pq.end());

 ll yes=0,no=1000001;
 while(yes+1<no) {
  ll mid=(yes+no)/2;
  
  bool flag=true;
  // solve at mid
  ll cur=0, ptr=0, res=mid;
  for(int i=1;i<=n;i++) {
   cur+=a[i];
   cur-=res*b[i];
   if(cur<0) {flag=false; break;}
   if(pq[ptr].second==i) {
    int ok=cur/c[i];
    while(ok && i!=n && (res-ok)*b[i+1]>a[i+1]+cur-c[i]*ok) ok--;
    res-=ok; cur-=c[i]*ok;
    if(res<=0) break;

    ptr++;
    while(pq[ptr].second<i) ptr++;
   }
  }
  
  if(flag && res<=0) yes=mid;
  else no=mid;
 }
 cout << yes << "\n";
}
int main() {
 ios::sync_with_stdio(false);
 cin.tie(0);
 for(cin >> tc;tc--;)solve();
}

提出情報

ジャッジ結果