TopCoder SRM 616 Div1 Easy WakingUp

概要

今眠さがSより高いなら絶対に寝ないでください.眠すぎて永眠してしまいます

問題概要

毎分D眠さが深まるあなたを,N個のアラームが起こそうとする.i個目のアラームはb_i分からa_i分ごとにc_i眠気を覚ます.
寝てもいつか起きてしまう(=眠さが0以下になる)初期眠さSの最大値を求めよ.

解法

a_i\leq 10より,lcm(1,2,3,...,10)=2520分の約数分周期になる.
これがわかれば二分探索で,5040分以内に起きるか,2520分時点より5040分時点での眠りが深ければその初期眠さではいつかおきることができる.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
using Pl=pair<ll,ll>;
using PPl=pair<ll,Pl>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
class WakingUp{
public:
    int maxSleepiness(vi a,vi b,vi c,int d){
        int n=a.size();
        ll g=2520;
        ll ok=0,ng=LINF;
        while(ng-ok>1){
            ll mid=(ng+ok)/2;
            ll x=mid;
            bool f=false;
            for(int i=1;i<=g;i++){
                x+=d;
                REP(j,n){
                    if(i>=b[j]&&(i-b[j])%a[j]==0){
                        x-=c[j];
                    }
                }
                if(x<=0){
                    f=true;
                    break;
                }
            }
            if(f){
                ok=mid;
                continue;
            }
            ll y=x;
            for(int i=g+1;i<=g*2;i++){
                x+=d;
                REP(j,n){
                    if(i>=b[j]&&(i-b[j])%a[j]==0){
                        x-=c[j];
                    }
                }
                if(x<=0){
                    f=true;
                    break;
                }
            }
            if(f){
                ok=mid;
                continue;
            }
            if(x<y){
                ok=mid;
            }else{
                ng=mid;
            }
        }
        return ok==LINF-1?-1:ok;
    }
};