oj.uz

Submission #229703

# Submission time Handle Problem Language Result Execution time Memory
229703 2020-05-06T00:32:31 Z monus1042 Rice Hub (IOI11_ricehub) C++17
0 / 100
 9 ms 640 KB 
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

int besthub(int R, int L, int X[], long long B)	{
	int ans=1;
	ll cost=0;

	ll pref[R];
	for (ll i=0; i<R; i++){
		if (!i)
			pref[i] = X[i];
		else
			pref[i] = pref[i-1] + X[i];
	}

	ll l=R-1;
	for (int i=R-2; ~i; i--){
		if (cost + (ll)(X[R-1] - X[i]) <= B){
			l--;
			cost+=(ll)(X[R-1] - X[i]);
			ans++;
		}else break;
	}

	for (ll i=R-2; ~i; i--){
		ll dist=X[i+1] - X[i];
		if (l>i){
			l=i;
		}else{
			cost -= dist + (i+1-l);
		}
		ll lo=i, hi=R;
		while(lo+1!=hi){
			ll en=(lo + hi)/2;
			ll cost2=pref[en] - pref[i] - (en-i)*(ll)X[i];
			if (cost + cost2 <= B)
				lo=en;
			else
				hi=en;
		}
		int currans=lo-l+1;
		ll currcost = cost + pref[lo] - pref[i] - (lo-i)*(ll)(X[i]);

		int newl=l;
		//bool ok=0;
		ll auxcost=cost;
		//while(1){
		//if (ok) break;
			if (newl - 1 >= 0){
				while(1){
					if (newl - 1 >= 0 && auxcost + (X[i] - X[newl-1]) <= B){
						newl--;
						auxcost += (ll)(X[i] - X[newl]);
						ll lo1=i, hi1=R;
						while(lo1+1!=hi1){
							ll en=(lo1 + hi1)/2;
							ll cost2=pref[en] - pref[i] - (en-i)*(ll)X[i];
							if (auxcost + cost2 <= B)
								lo1=en;
							else
								hi1=en;
						}
						ll cans = lo1 - newl + 1;
						ll ccost= auxcost + pref[lo1] - pref[i] - (lo1-i)*(ll)(X[i]);
						
						if (cans == currans && ccost <= currcost){
							currcost = ccost;
							l=newl;
							cost = auxcost;
						}else if (cans > currans){
							currcost=ccost;
							currans = cans;
							l=newl;
							cost=auxcost;
						}else{
							break;
						}
					}else{
						break;
					}
				}
			}
			//}
			ans=max(ans, currans);
	}

	return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Incorrect 5 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -