Submission #3596

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3596	2013-08-31T06:47:53 Z	sjw0687	King of penalty (kriii1_K)	C++	0 / 1	68 ms	2844 KB

K

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;

typedef long long llong;

int p, n;
int timeProb[100001];
llong sumT[100001];
int numSolve;

int main(void)
{
	cin >> p >> n;
	for(int i=1; i<=n; i++) {
		cin >> timeProb[i];
	}
	sort(timeProb+1, timeProb+(n+1));
	for(int i=1; i<=n; i++) {
		sumT[i] = sumT[i-1] + timeProb[i];
		if( sumT[i] < p )
			numSolve = i;
	}

	llong timeProbAnswer = 0;
	for(int i=1; i <= n - numSolve + 1; i++) {
		int first = i;
		int last = i+numSolve-1;
		llong totalT = sumT[last] - sumT[first-1];
		llong preT = p - totalT - 1;

		if( totalT >= p ) break;
		llong t = 0;
		t += preT * numSolve;
		for(int j=last; j>=first; j--) {
			int cnt = j - first + 1;
			t += cnt * timeProb[j];
		}
		if( t > timeProbAnswer )
			timeProbAnswer = t;
	}
	
	cout << numSolve << ' ' << timeProbAnswer << endl;

	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2844 KB	Output is correct
2	Correct	0 ms	2844 KB	Output is correct
3	Correct	0 ms	2844 KB	Output is correct
4	Correct	8 ms	2844 KB	Output is correct
5	Correct	0 ms	2844 KB	Output is correct
6	Correct	8 ms	2844 KB	Output is correct
7	Correct	24 ms	2844 KB	Output is correct
8	Correct	24 ms	2844 KB	Output is correct
9	Correct	68 ms	2844 KB	Output is correct
10	Correct	64 ms	2844 KB	Output is correct
11	Correct	32 ms	2844 KB	Output is correct
12	Correct	20 ms	2844 KB	Output is correct
13	Incorrect	0 ms	2844 KB	Output isn't correct
14	Halted	0 ms	0 KB	-