洛谷P 1280ニックのミッション

テーマ:ニックのミッション
考え方:
順序を逆にして並べ替えます.
f[i]は、i~nの稼働時間においてニックが得ることができる最大アイドル時間を示す.
f[i]=max((f[i+a[h].t]),f[i]),h∈{ x | a[x].p == i }
コード:

#include
using namespace std;

#define maxn 10000

struct Work{
	int p,t,q;
	Work(int pp=0,int tt=0) {
		p=pp,t=tt;
		q=p+t;
	}
	bool operator B.p;
	}
};

int n,k;

Work a[maxn+5];
int s[maxn+5]={0}; 
int f[maxn+5]={0};

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++){
		int p,t;
		scanf("%d%d",&p,&t);
		a[i]=Work(p,t);
		s[p]++;
	}
	sort(a+1,a+k+1);
	
	int h=1;	
	for(int i=n;i>=1;i--){
		if(!s[i]) f[i]=f[i+1]+1;
		else {
			for(int j=s[i];j>=1;j--){
				f[i]=max((f[i+a[h].t]),f[i]);
				h++;
			}
		}
	}
	
	printf("%d",f[1]);
	
	return 0;
}