Submission #1171067

#TimeUsernameProblemLanguageResultExecution timeMemory
1171067owieczkaTwo Dishes (JOI19_dishes)C++20
0 / 100
10095 ms9740 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll time1[1'000'003];
ll time2[1'000'003];
ll crit1[1'000'003];
ll crit2[1'000'003];
ll pts1[1'000'003];
ll pts2[1'000'003];

ll dp[2'002][2'002];

int main()
{
   ios::sync_with_stdio(0); cin.tie(0);
   ll n, m;
   cin >> n >> m;
   bool sub1 = 1;
   for (ll i = 1; i <= n; i++)
   {
      cin >> time1[i] >> crit1[i] >> pts1[i];
      if (i && crit1[i] != crit1[i-1])sub1 = 0;
      time1[i] += time1[i-1];
   }
   for (ll i = 1; i <= m; i++)
   {
      cin >> time2[i] >> crit2[i] >> pts2[i];
      if (i && crit2[i] != crit2[i-1])sub1 = 0;
      time2[i] += time2[i-1];
   }
   ll ans = 0;
   if (n <= 2e3 && m <= 2e3)
   {
      dp[1][0] = !!(time1[1]<=crit1[1]);
      dp[0][1] = !!(time2[1]<=crit2[1]);
      for (ll i = 1; i <= n; i++)
      {
         for (ll j = 1; j <= m; j++)
         {
            dp[i][j] = max(dp[i-1][j] + !!(time1[i]+time2[j] <= crit1[i]), dp[i][j-1] + !!(time1[i]+time2[j] <= crit2[j]));
         }
      }
      ans = dp[n][m];
   }
   else 
   {
      for (ll i = 1; i <= m; i++)
         pts2[i] += pts2[i-1];
      for (ll i = 1; i <= n; i++)
         pts1[i] += pts1[i-1];
      ll c = crit1[1];
      ll j = 0;
      for (ll i = n; i > 0; i++)
      {
         if (time1[i] > c)continue;
         while(time2[j+1] + time1[i] <= c)
         {
            j++;
         }
         ans = max(ans, pts1[i] + pts2[j]);
      }
   }
   cout << ans << '\n';
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...