oj.uz

Submission #157196

# Submission time Handle Problem Language Result Execution time Memory
157196 2019-10-10T03:20:35 Z DrumpfTheGodEmperor 스트랩 (JOI14_straps) C++14
45 / 100
 53 ms 32032 KB 
#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4485090715960753727;
const int N = 2005;
int n, dp[N][N];
struct Line {
	int a, b;
	bool operator<(const Line &rhs) const { return a > rhs.a; }
} l[N];
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	fw (i, 0, n) cin >> l[i].a >> l[i].b;
	sort(l, l + n);
	//If we have the subset we want, sort the vertexes in decreasing max children.
	memset(dp, -63, sizeof dp);
	dp[0][1] = 0;
	fw (i, 0, n) fw (j, 1, n + 1) if (dp[i][j] != -infll) {
		//We can have j more children.
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
		dp[i + 1][j - 1 + l[i].a] = max(dp[i + 1][j - 1 + l[i].a], dp[i][j] + l[i].b);
	}
	int ans = 0;
	fw (i, 1, n + 1) fw (j, 0, n + 1) ans = max(ans, dp[i][j]);
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31864 KB Output is correct
2 Correct 29 ms 31864 KB Output is correct
3 Correct 29 ms 31724 KB Output is correct
4 Correct 28 ms 31836 KB Output is correct
5 Correct 29 ms 31864 KB Output is correct
6 Correct 35 ms 31812 KB Output is correct
7 Correct 29 ms 31736 KB Output is correct
8 Correct 29 ms 31768 KB Output is correct
9 Correct 29 ms 31736 KB Output is correct
10 Correct 29 ms 31736 KB Output is correct
11 Correct 29 ms 31736 KB Output is correct
12 Correct 28 ms 31736 KB Output is correct
13 Correct 28 ms 31784 KB Output is correct
14 Correct 29 ms 31864 KB Output is correct
15 Correct 28 ms 31728 KB Output is correct
16 Correct 29 ms 31744 KB Output is correct
17 Correct 29 ms 31864 KB Output is correct
18 Correct 29 ms 31736 KB Output is correct
19 Correct 28 ms 31864 KB Output is correct
20 Correct 29 ms 31864 KB Output is correct
21 Correct 29 ms 31804 KB Output is correct
22 Correct 29 ms 31724 KB Output is correct
23 Correct 28 ms 31736 KB Output is correct
24 Incorrect 28 ms 31864 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31996 KB Output is correct
2 Correct 29 ms 31880 KB Output is correct
3 Correct 29 ms 31736 KB Output is correct
4 Correct 29 ms 31864 KB Output is correct
5 Correct 29 ms 31836 KB Output is correct
6 Correct 29 ms 31864 KB Output is correct
7 Correct 29 ms 31736 KB Output is correct
8 Correct 33 ms 31864 KB Output is correct
9 Correct 32 ms 31868 KB Output is correct
10 Correct 32 ms 31864 KB Output is correct
11 Correct 32 ms 31864 KB Output is correct
12 Correct 41 ms 31864 KB Output is correct
13 Correct 42 ms 31900 KB Output is correct
14 Correct 41 ms 31864 KB Output is correct
15 Correct 41 ms 31868 KB Output is correct
16 Correct 40 ms 31836 KB Output is correct
17 Correct 41 ms 31864 KB Output is correct
18 Correct 41 ms 31864 KB Output is correct
19 Correct 46 ms 31864 KB Output is correct
20 Correct 47 ms 31932 KB Output is correct
21 Incorrect 52 ms 31864 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31920 KB Output is correct
2 Correct 35 ms 31736 KB Output is correct
3 Correct 29 ms 31836 KB Output is correct
4 Correct 29 ms 31864 KB Output is correct
5 Correct 28 ms 31864 KB Output is correct
6 Correct 29 ms 31864 KB Output is correct
7 Correct 29 ms 31864 KB Output is correct
8 Correct 29 ms 31864 KB Output is correct
9 Correct 32 ms 31864 KB Output is correct
10 Correct 32 ms 31864 KB Output is correct
11 Correct 31 ms 31864 KB Output is correct
12 Correct 32 ms 31876 KB Output is correct
13 Correct 32 ms 31864 KB Output is correct
14 Correct 32 ms 31916 KB Output is correct
15 Correct 32 ms 31864 KB Output is correct
16 Correct 32 ms 31864 KB Output is correct
17 Correct 40 ms 31864 KB Output is correct
18 Correct 41 ms 31864 KB Output is correct
19 Correct 41 ms 31864 KB Output is correct
20 Correct 40 ms 31864 KB Output is correct
21 Correct 42 ms 31864 KB Output is correct
22 Correct 42 ms 31864 KB Output is correct
23 Correct 40 ms 31864 KB Output is correct
24 Correct 41 ms 31864 KB Output is correct
25 Correct 41 ms 31864 KB Output is correct
26 Correct 40 ms 31808 KB Output is correct
27 Correct 40 ms 31824 KB Output is correct
28 Correct 41 ms 31864 KB Output is correct
29 Correct 42 ms 31864 KB Output is correct
30 Correct 40 ms 31864 KB Output is correct
31 Correct 40 ms 31912 KB Output is correct
32 Correct 41 ms 31884 KB Output is correct
33 Correct 40 ms 31864 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 32032 KB Output is correct
2 Correct 45 ms 31864 KB Output is correct
3 Correct 46 ms 31864 KB Output is correct
4 Correct 52 ms 31868 KB Output is correct
5 Correct 52 ms 31864 KB Output is correct
6 Correct 52 ms 31864 KB Output is correct
7 Correct 53 ms 31864 KB Output is correct
8 Correct 52 ms 31864 KB Output is correct
9 Incorrect 51 ms 31864 KB Output isn't correct
10 Halted 0 ms 0 KB -