Submission #804749

#	Time	Username	Problem	Language	Result	Execution time	Memory
804749		flappybird	Fun Palace (CCO18_fun)	C++17	25 / 25	66 ms	79356 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010
#define MAXS 20
#define INF 1000000000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
int A[MAX];
int B[MAX];
int dp[MAX][20010];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, E;
	cin >> N >> E;
	int i, j;
	int U = E - 1;
	for (i = 2; i <= N; i++) {
		cin >> A[i] >> B[i];
		U = max(U, A[i] + B[i]);
	}
	fill(&dp[0][0], &dp[MAX - 1][MAX], -INF);
	for (i = 0; i < E; i++) dp[1][i] = i;
	for (i = 2; i <= N; i++) {
		int mx = 0;
		for (j = 0; j < A[i]; j++) mx = max(mx, dp[i - 1][j]);
		for (j = 0; j < B[i]; j++) dp[i][j] = max(dp[i][j], mx + j);
		for (j = A[i] + B[i]; j <= U; j++) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		for (j = A[i]; j < A[i] + B[i]; j++) dp[i][j - A[i]] = max(dp[i][j - A[i]], dp[i - 1][j]);
		for (j = 0; j < A[i]; j++) dp[i][B[i] + j] = max(dp[i][B[i] + j], dp[i - 1][j] + B[i]);
	}
	int mx = 0;
	for (i = 0; i <= U; i++) mx = max(mx, dp[N][i]);
	cout << mx;
}

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