Submission #3602

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3602	2013-08-31T06:51:51 Z	sjw0687	King of penalty (kriii1_K)	C++	1 / 1	64 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 tAnswer = 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--) {
			llong cnt = j - first + 1;
			t += cnt * timeProb[j];
		}
		if( t > tAnswer )
			tAnswer = t;
	}
	
	cout << numSolve << ' ' << tAnswer << endl;

	return 0;
}

Subtask #1

1.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	28 ms	2844 KB	Output is correct
9	Correct	64 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	Correct	0 ms	2844 KB	Output is correct
14	Correct	4 ms	2844 KB	Output is correct
15	Correct	24 ms	2844 KB	Output is correct