oj.uz

Submission #955264

# Submission time Handle Problem Language Result Execution time Memory
955264 2024-03-30T02:21:06 Z yellowtoad 스트랩 (JOI14_straps) C++17
0 / 100
 23 ms 31836 KB 
#include <iostream>
#include <algorithm>
#define f first
#define s second
using namespace std;

long long n, x, y, dp[2010][2010], maxx;

int main() {
	cin >> n;
	dp[0][0] = -1e18;
	for (int i = 2; i <= n; i++) dp[0][i] = -1e18;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y;
		for (int j = 0; j < n; j++) {
			dp[i][j] = dp[i-1][j];
			if (j-x+1 >= 0) dp[i][j] = max(dp[i][j],dp[i-1][j-x+1]+y);
		}
		dp[i][n] = dp[i-1][n];
		for (int j = n-x+1; j <= n; j++) dp[i][n] = max(dp[i][n],dp[i-1][j]+y);
	}
	for (int i = 0; i <= n; i++) maxx = max(maxx,dp[n][i]);
	cout << maxx << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2492 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 1 ms 2496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 31836 KB Output isn't correct
2 Halted 0 ms 0 KB -