Submission #1337018

#TimeUsernameProblemLanguageResultExecution timeMemory
1337018rafsanamin2020Bouquet (EGOI24_bouquet)C++20
0 / 100
13 ms3264 KiB
#include <bits/stdc++.h>
#define l first
#define r second

using namespace std;

int solve3()
{
  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});
  }

  for (int i = 1; i < K; i++)
  {
    if (i > Q[i].l)
    {
      for (int j = 0; j < i - Q[i].l; j++)
      {
        if (j + Q[j].r < i)
        {
          // cout << i << " " << j << "\n";
          dp[i] = max(dp[i], dp[j] + 1);
        }
      }
    }
  }

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

  return *max_element(dp.begin(), dp.end());
}
int solve4()
{
  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});
  }

  for (int i = 1; i < K; i++)
  {
    if (i > 2)
      dp[i] = dp[i - 3] + 1;

    for (int j = 2; j > Q[i].l; j--)
    {
      if (i - j >= 0 && j + Q[i - j].r < i)
      {
        dp[i] = max(dp[i - j] + 1, dp[i]);
      }
    }
  }

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

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

  cout << solve4();
}
#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...