SRM 588 div 1

easy撃墜されて0pointだった
1225 -> 1194

easy
N=1のケースで撃墜されるコードを書いてしまった。
DP思いつかない人なので貪欲で解いた。
最大m個の歌を歌えるとして
a1, a2, a3, ... , am
の歌を歌うのにかかる時間Sは
S = Σ(duration) + Σ(wait_time)
= Σ(duration) + max(tone[ai]) - min(tone[aj])
となるので、歌をtoneでソートしてmaxとminのtoneを決めてしまってから、そのtoneの範囲にある歌のdurationを小さい順に合計がTを超えるまで見ていけばいい。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define F first
#define S second
typedef pair<int, int> P;
 
class GUMIAndSongsDiv1{
public:
	P songs[50];
	int N;
	int solve(int p, int q, int T){
		int dur[50];
		int m = q - p + 1;
		for(int i = p; i <= q; i++){
			dur[i-p] = songs[i].S;
		}
		sort(dur, dur + m);
		int sum = 0;
		rep(i, m){
			sum += dur[i];
			if(sum > T) return i;
		}
		return m;
	}
	int maxSongs(vector <int> duration, vector <int> tone, int T){
		N = tone.size();
		rep(i, N){
			songs[i].F = tone[i];
			songs[i].S = duration[i];
		}
		sort(songs, songs + N);
		int ans = 0;
		rep(i, N){
			for(int j = i; j < N; j++){
				int sw = songs[j].F - songs[i].F;
				ans = max(ans, solve(i, j, T - sw));
			}
		}
		return ans;
	}
};