abc023_d

結構悩んで解いた問題。

解説を読んでも

if(t[i] < i) flg = false;

の部分がずっとハテナだったけどt[i]はデッドラインだからデッドラインが今割るべき時間iより小さかったらNG

#include<bits/stdc++.h>

using namespace std;

int n, h[100009], s[100009];

int main(){

cin >> n;

for(int i=0;i<n;i++) cin >> h[i] >> s[i];

long long int ng = 0, ok = 100000000000009;

while(abs(ok - ng) > 1){

long long int mid = (ok + ng)/2;

vector < long long int > t;

bool flg = true;

for(int i=0;i<n;i++){

if(mid >= h[i]) t.push_back*1;

for(int i=0;i<n;i++){

//cout << t[i] << endl;

if(t[i] < i) flg = false;

}

}

if(flg) ok = mid;

else ng = mid;

//cout << mid << " " << flg << endl;

}

cout << ok << endl;

}

*1:mid-h[i])/s[i]);

else flg = false;

}

if(flg){

sort(t.begin(), t.end(