This was the first time I implement ternary search, I figured out what it is, and how it matches to 215D - Hot Days, however, I keep getting Wrong answer on test 15 which seems to be common for a some of the other contestants as well (http://www.codeforces.com/contest/215/status)
Could someone help me please to figure out the bug in my solution ?
#define ll long long
ll n,m;
ll z,ti,Ti,xi,costi;
ll f(ll y) { // cost if got y buses
ll slc=m-((y-1ll)*z);
ll e=slc>z?(slc*xi):0ll;
return (y*costi)+e;
}
ll r(ll a,ll b) { // ternary search
assert(b>=a);
if((b-a)==0) return f(a);
if((b-a)==1) return min(f(a),f(b));
ll x=a+(b-a)/3;
ll y=b-(b-a)/3;
assert(x<y);
if(f(x)>=f(y)) return r(x+1,b);
return r(a,y-1);
}
int main() {
// freopen("me.txt","r",stdin);
cin>>n>>m;
ll res=0;
for(int i=0;i<n;++i) {
cin>>ti>>Ti>>xi>>costi;
if(Ti>ti) {
z=Ti-ti; //maximum capacity per bus, except last bus
ll g=round(ceil((double)m/z)); // maximum number of buses
res+=r(1ll,g);
} else {
res+=(costi+(m*xi));
}
}
cout<<res<<endl;
return 0;
}
Thanks a lot :)
Edit: I managed to get AC when I brute forced the entire interval when b-a < 1000 (got WA on case 29 when tried b-a < 100):
if(b-a < 1000) {
ll res=f(a);
for(int i=a+1;i<=b;++i) res=min(res,f(i));
return res;
}