SRM 582 div 2

1116 -> 1217
青色になりました。
当面の目標は緑に下がらないこと。

easy

#include <cstdio>
#include <string>
using namespace std;

class SemiPerfectSquare{
public:
	string check(int N){
		bool f = 0;
		for(int a = 1; a <= N; a++){
			for(int b = a + 1; a * b * b <= N; b++){
				if(a * b * b == N) return "Yes";
			}
		}
		return "No";
	}
};

med
貪欲法を使う。
強い魔法少女は強い敵と戦うようにしていく

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

typedef pair<int, int> E;
class SpaceWarDiv2{
public:
	int minimalFatigue(vector <int> gs, vector <int> es, vector <int> ec){
		sort(gs.begin(), gs.end());
		reverse(gs.begin(), gs.end());
		vector<E> e;
		int sum = 0;
		for(int i = 0; i < es.size(); i++){
			e.push_back(E(es[i], ec[i]));
			sum += ec[i];
		}
		sort(e.begin(), e.end());
		reverse(e.begin(), e.end());
		
		if(e[0].first > gs[0]) return -1;
		int t;
		for(t = 1; ; t++){
			for(int i = 0; i < gs.size(); i++){
				for(int j = 0; j < e.size(); j++){
					if(e[j].second > 0 && e[j].first <= gs[i]){
						e[j].second--;
						sum--;
						if(sum == 0){
							return t;
						}
						break;
					}
				}
			}
		}
	}
};