Submission #1057401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057401		juicy	스트랩 (JOI14_straps)	C++17	100 / 100	12 ms	32088 KiB

straps

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e3 + 5;
const long long inf = 1e18;

int n;
long long dp[N][N];
array<int, 2> a[N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i][0] >> a[i][1];
  }
  sort(a + 1, a + n + 1, [&](const auto &a, const auto &b) {
    return a[0] > b[0];
  });
  for (int i = 0; i <= n; ++i) {
    fill(dp[i], dp[i] + n + 1, -inf);
  }
  dp[0][1] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (dp[i][j] != -inf) {
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        int k = min(n, j + a[i + 1][0] - 1);
        if (k >= 0) {
          dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i + 1][1]);
        }
      }
    }
  } 
  cout << *max_element(dp[n], dp[n] + n + 1);
  return 0;
}

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