TopCoder SRM 800 : Div1 Medium MaximumPenalty

なんだこの制限…。
https://community.topcoder.com/stat?c=problem_statement&pm=16823&rd=18497

問題

N個の仕事がある。
各仕事wは、かかる時間L[w]が与えられる。
また、それぞれ完了時刻tの3次式の形でペナルティが設定される。

仕事を任意の順で1つずつ行ったとき、ペナルティの最大値を最小化したい。
そのような仕事順の例を求めよ。

解法

最大ペナルティを二分探索しよう。
最大ペナルティを求めると、仕事wを始めるべき時間S[w]が計算できる。

あとはよくある、何らかの基準で仕事の順をソートする問題に落ちる。
今時刻tである場合、仕事iをjより先に行う場合はt≦min(S[i],S[j]-L[i])でなければならず、jを先に行うにはt≦min(S[i],S[j]-L[i])でなければならない。
iを先に行う方がよい条件は、S[j]-L[i]≧S[i]-L[j]なので、変形するとS[j]+L[j]≧S[i]+L[i]となる。
よって、仕事をS[w]+L[w]の昇順に並べるとよい。

値域が微妙に広いので、探索範囲やオーバーフローに注意。
自分はこれで落とした…。

typedef unsigned long long ull;
vector <int> L;
vector <int> P;
int N;
ll S[1010];
class MaximumPenalty {
	public:
	ull tim(int i,ull s) {
		if(s>100000) return 1ULL<<63;
		return P[4*i]+P[4*i+1]*s+P[4*i+2]*s*s+P[4*i+3]*s*s*s;
	}
	vector<int> ok(ll v) {
		int i,j;
		vector<pair<int,int>> P;
		FOR(i,N) {
			if(tim(i,L[i])>v) return {};
			S[i]=0;
			for(j=16;j>=0;j--) if(tim(i,S[i]+L[i]+(1<<j))<=v) S[i]+=1<<j;
			P.push_back({S[i]+L[i],i});
		}
		sort(ALL(P));
		ll cur=0;
		vector<int> R;
		FORR(p,P) {
			int i=p.second;
			cur+=L[i];
			if(tim(i,cur)>v) return {};
			R.push_back(i);
		}
		return R;
		
	}
	
	vector <int> schedule(vector <int> L, vector <int> P) {
		::L=L;
		::P=P;
		N=L.size();
		
		ll ret=(1ULL<<63)-1;
		vector<int> V,R;
		for(int i=62;i>=0;i--) {
			V=ok(ret-(1ULL<<i));
			if(V.size()) {
				R=V;
				ret-=1ULL<<i;
			}
		}
		return R;
		
	}
}

まとめ

こんなギリギリの計算させる意図何なんだろ。
何も面白さに結びつかない…。