제출 #1203594

#제출 시각아이디문제언어결과실행 시간메모리
1203594rafsanamin2020Bouquet (EGOI24_bouquet)C++20
8 / 100
20 ms3264 KiB
#include <bits/stdc++.h>
#define l first;
#define r second;

using namespace std;

int solve1()
{
  int K;
  vector<pair<int, int>> Q;
  cin >> K;
  for (int i = 0; i < K; i++)
  {
    int L, R;
    cin >> L >> R;
    Q.push_back({L, R});
  }

  int v = Q[0].l;

  ++v;
  return (K / v) + (K % v == 0 ? 0 : 1);
}

int solve2()
{
  int K;
  vector<pair<int, int>> Q;
  cin >> K;
  vector<int> dp(K, 1);
  for (int i = 0; i < K; i++)
  {
    int L, R;
    cin >> L >> R;
    Q.push_back({L, R});
  }
  reverse(Q.begin(), Q.end());

  for (int i = 0; i < K; i++)
  {
    int idx = i + 1 + Q[i].first;
    if (idx < K)
    {
      dp[idx] = max(dp[idx], dp[i] + 1);
    }
  }

  // for (int x : dp)
  // {
  //   cout << x << " ";
  // }

  return *max_element(dp.begin(), dp.end());
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cout << solve2();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...