Submission #105708

#	Time	Username	Problem	Language	Result	Execution time	Memory
105708		Pro_ktmr	스트랩 (JOI14_straps)	C++14	100 / 100	58 ms	16256 KiB

straps

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int N;
vector<pair<int,int> > items;
int dp[2000][2000];
int solve(int now, int p){
	if(now == N) return 0;
	if(p > N-now) return solve(now,N-now);
	if(p == 0) return 0;
	if(dp[now][p] != -1) return dp[now][p];
	return dp[now][p] = max(solve(now+1,p),solve(now+1,p-1+items[now].first)+items[now].second);
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	cin >> N;
	for(int i=0;i <N; i++){
		int A,B;
		cin >> A >> B;
		items.push_back(MP(A,B));
		for(int j=0; j<N; j++) dp[i][j] = -1;
	}
	sort(items.begin(), items.end());
	reverse(items.begin(), items.end());

	cout << solve(0,1) << endl;

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 45 / 45
• Subtask 4: 45 / 45