# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

157200 | 2019-10-10T03:25:16 Z | EntityIT | 스트랩 (JOI14_straps) | C++14 | 56 ms | 31952 KB |

#include<bits/stdc++.h> using namespace std; using LL = long long; const LL infLL = (LL)1e18 + 123; const int N = (int)2e3 + 5; int n; LL f[N][N]; struct Str { int a, b; Str(int _a = 0, int _b = 0) : a(_a), b(_b) {} bool operator<(const Str &_) const { return a > _.a; } } str[N]; int main() { scanf(" %d", &n); for (int i = 1; i <= n; ++i) scanf(" %d %d", &str[i].a, &str[i].b); sort(str + 1, str + n + 1); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) f[i][j] = -infLL; } f[0][1] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= n; ++j) if (f[i][j] > -infLL) { f[i + 1][j] = max(f[i + 1][j], f[i][j]); if (j) { int nJ = j - 1 + str[i + 1].a; if (nJ > n) nJ = n; f[i + 1][nJ] = max(f[i + 1][nJ], f[i][j] + str[i + 1].b); } } } LL ans = -infLL; for (int j = 0; j <= n; ++j) ans = max(ans, f[n][j]); cout << ans << '\n'; return 0; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 28 ms | 31736 KB | Output is correct |

2 | Correct | 28 ms | 31836 KB | Output is correct |

3 | Correct | 28 ms | 31812 KB | Output is correct |

4 | Correct | 29 ms | 31836 KB | Output is correct |

5 | Correct | 28 ms | 31836 KB | Output is correct |

6 | Correct | 33 ms | 31736 KB | Output is correct |

7 | Correct | 37 ms | 31836 KB | Output is correct |

8 | Correct | 28 ms | 31736 KB | Output is correct |

9 | Correct | 33 ms | 31736 KB | Output is correct |

10 | Correct | 32 ms | 31736 KB | Output is correct |

11 | Correct | 31 ms | 31864 KB | Output is correct |

12 | Correct | 28 ms | 31912 KB | Output is correct |

13 | Correct | 28 ms | 31736 KB | Output is correct |

14 | Correct | 27 ms | 31736 KB | Output is correct |

15 | Correct | 27 ms | 31736 KB | Output is correct |

16 | Correct | 27 ms | 31736 KB | Output is correct |

17 | Correct | 27 ms | 31728 KB | Output is correct |

18 | Correct | 27 ms | 31736 KB | Output is correct |

19 | Correct | 27 ms | 31736 KB | Output is correct |

20 | Correct | 27 ms | 31736 KB | Output is correct |

21 | Correct | 34 ms | 31736 KB | Output is correct |

22 | Correct | 28 ms | 31736 KB | Output is correct |

23 | Correct | 28 ms | 31736 KB | Output is correct |

24 | Correct | 28 ms | 31736 KB | Output is correct |

25 | Correct | 27 ms | 31716 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 28 ms | 31864 KB | Output is correct |

2 | Correct | 28 ms | 31736 KB | Output is correct |

3 | Correct | 28 ms | 31736 KB | Output is correct |

4 | Correct | 28 ms | 31736 KB | Output is correct |

5 | Correct | 28 ms | 31736 KB | Output is correct |

6 | Correct | 28 ms | 31864 KB | Output is correct |

7 | Correct | 28 ms | 31864 KB | Output is correct |

8 | Correct | 30 ms | 31736 KB | Output is correct |

9 | Correct | 30 ms | 31864 KB | Output is correct |

10 | Correct | 30 ms | 31736 KB | Output is correct |

11 | Correct | 30 ms | 31736 KB | Output is correct |

12 | Correct | 35 ms | 31812 KB | Output is correct |

13 | Correct | 35 ms | 31736 KB | Output is correct |

14 | Correct | 37 ms | 31840 KB | Output is correct |

15 | Correct | 36 ms | 31736 KB | Output is correct |

16 | Correct | 36 ms | 31736 KB | Output is correct |

17 | Correct | 36 ms | 31736 KB | Output is correct |

18 | Correct | 36 ms | 31736 KB | Output is correct |

19 | Correct | 45 ms | 31736 KB | Output is correct |

20 | Correct | 47 ms | 31836 KB | Output is correct |

21 | Correct | 56 ms | 31736 KB | Output is correct |

22 | Correct | 39 ms | 31736 KB | Output is correct |

23 | Correct | 56 ms | 31736 KB | Output is correct |

24 | Correct | 39 ms | 31736 KB | Output is correct |

25 | Correct | 54 ms | 31736 KB | Output is correct |

26 | Correct | 47 ms | 31864 KB | Output is correct |

27 | Correct | 53 ms | 31736 KB | Output is correct |

28 | Correct | 44 ms | 31736 KB | Output is correct |

29 | Correct | 47 ms | 31736 KB | Output is correct |

30 | Correct | 43 ms | 31876 KB | Output is correct |

31 | Correct | 42 ms | 31736 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 27 ms | 31836 KB | Output is correct |

2 | Correct | 27 ms | 31736 KB | Output is correct |

3 | Correct | 28 ms | 31736 KB | Output is correct |

4 | Correct | 27 ms | 31740 KB | Output is correct |

5 | Correct | 27 ms | 31736 KB | Output is correct |

6 | Correct | 28 ms | 31736 KB | Output is correct |

7 | Correct | 28 ms | 31836 KB | Output is correct |

8 | Correct | 28 ms | 31836 KB | Output is correct |

9 | Correct | 31 ms | 31736 KB | Output is correct |

10 | Correct | 30 ms | 31836 KB | Output is correct |

11 | Correct | 30 ms | 31792 KB | Output is correct |

12 | Correct | 31 ms | 31736 KB | Output is correct |

13 | Correct | 31 ms | 31792 KB | Output is correct |

14 | Correct | 30 ms | 31808 KB | Output is correct |

15 | Correct | 30 ms | 31736 KB | Output is correct |

16 | Correct | 30 ms | 31736 KB | Output is correct |

17 | Correct | 37 ms | 31736 KB | Output is correct |

18 | Correct | 37 ms | 31736 KB | Output is correct |

19 | Correct | 36 ms | 31836 KB | Output is correct |

20 | Correct | 42 ms | 31836 KB | Output is correct |

21 | Correct | 38 ms | 31736 KB | Output is correct |

22 | Correct | 38 ms | 31864 KB | Output is correct |

23 | Correct | 36 ms | 31736 KB | Output is correct |

24 | Correct | 35 ms | 31736 KB | Output is correct |

25 | Correct | 36 ms | 31736 KB | Output is correct |

26 | Correct | 35 ms | 31736 KB | Output is correct |

27 | Correct | 35 ms | 31736 KB | Output is correct |

28 | Correct | 36 ms | 31844 KB | Output is correct |

29 | Correct | 38 ms | 31736 KB | Output is correct |

30 | Correct | 36 ms | 31736 KB | Output is correct |

31 | Correct | 36 ms | 31828 KB | Output is correct |

32 | Correct | 37 ms | 31864 KB | Output is correct |

33 | Correct | 36 ms | 31836 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 43 ms | 31740 KB | Output is correct |

2 | Correct | 44 ms | 31784 KB | Output is correct |

3 | Correct | 46 ms | 31736 KB | Output is correct |

4 | Correct | 41 ms | 31736 KB | Output is correct |

5 | Correct | 56 ms | 31952 KB | Output is correct |

6 | Correct | 55 ms | 31736 KB | Output is correct |

7 | Correct | 55 ms | 31736 KB | Output is correct |

8 | Correct | 53 ms | 31784 KB | Output is correct |

9 | Correct | 54 ms | 31740 KB | Output is correct |

10 | Correct | 55 ms | 31840 KB | Output is correct |

11 | Correct | 55 ms | 31788 KB | Output is correct |

12 | Correct | 54 ms | 31776 KB | Output is correct |

13 | Correct | 53 ms | 31832 KB | Output is correct |

14 | Correct | 50 ms | 31864 KB | Output is correct |

15 | Correct | 54 ms | 31836 KB | Output is correct |

16 | Correct | 53 ms | 31740 KB | Output is correct |

17 | Correct | 55 ms | 31736 KB | Output is correct |

18 | Correct | 55 ms | 31736 KB | Output is correct |

19 | Correct | 43 ms | 31832 KB | Output is correct |

20 | Correct | 42 ms | 31736 KB | Output is correct |

21 | Correct | 43 ms | 31864 KB | Output is correct |

22 | Correct | 42 ms | 31736 KB | Output is correct |

23 | Correct | 43 ms | 31880 KB | Output is correct |

24 | Correct | 42 ms | 31736 KB | Output is correct |

25 | Correct | 44 ms | 31736 KB | Output is correct |