Submission #1171072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171072		owieczka	Two Dishes (JOI19_dishes)	C++20	10 / 100	10095 ms	31816 KiB

dishes

#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)
   {
      for (ll i = 0; i <= n; i++)
      {
         for (ll j = 0; j <= m; j++)
         {
            if (!i && !j)continue;
            if (!i)
            {
               dp[i][j] = dp[i][j-1] + !!(time1[i]+time2[j] <= crit2[j]);
            }
            else if (!j)
            {
               dp[i][j] = dp[i-1][j] + !!(time1[i]+time2[j] <= crit1[i]);
            }
            else 
               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';
}

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9