Codeforces Round #100 D : New Year Contest

問題概要

解くのにA[i]分必要な問題がN(<100)問ある。問題iをt分で解いたらmax(0, t-360)だけのペナルティが与えられる。720分でどれだけの問題が解けるか求め、そのうち最小のペナルティを求める問題。

解法

簡単な順に解けば良い。証明というほどではないが、小さい方からとれるだけとった方がよいのは相当に自明。順番については、確かに易->難の順序を入れ替えても得することはないように思える(適当)。

acceptされた、ごちゃごちゃしたコード

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_T = 720;
const int MAX_N = 100;

const int INF = 1<<29;

int N;
int as[MAX_N];
int bs[MAX_N];
pair<int,int> dp[MAX_T + 1];

int penalty(int t, int start){
	return max(0, t + start - 360);
}

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as + i);
	}
}

void solve_brute(){
	sort(as, as + N);

	pair<int,int> maxi(0, 0);
	do{
		int t = 10;
		pair<int,int> score(0, 0);
		for(int i=0; i<N; i++){
			t += as[i];
			if(t > 720){
				break;
			}
			score.first++;
			score.second -= max(0, t - 360);
		}

		if(score > maxi){
			maxi = score;
			memcpy(bs, as, sizeof(as));
		}
	}while(next_permutation(as, as+N));
	puts("");
	printf("%d %d\n", maxi.first, -maxi.second);
	for(int i=0; i<maxi.first; i++){
		printf("%d, ", bs[i]);
	}puts("");
	sort(as, as+N);
	for(int i=0; i<maxi.first; i++){
		printf("%d, ", as[i]);
	}puts("");
}

void solve(){
	sort(as, as + N);

	int t = 10, sol = 0, pen = 0;
	for(int i=0; i<N; i++){
		t += as[i];
		if(t > 720){
			break;
		}
		sol++;
		pen += max(0, t - 360);
	}

	printf("%d %d\n", sol, pen);
}

int main(){
	init();
	solve_brute();
	return 0;
}