Submission #1170879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170879		jerzyk	Two Dishes (JOI19_dishes)	C++20	10 / 100	10093 ms	39932 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<20;
int tim1[N], tim2[N];
ll sum1[N], sum2[N];
ll lim1[N], lim2[N];
int cst1[N], cst2[N];

ll dp[N];
vector<int> kon[N];
bool czy[N];

void E(int i)
{
    for(int j = 0; j < (int)kon[i].size(); ++j)
        czy[kon[i][j]] = 0;
}

ll DoDP(int n, int m)
{
    for(int i = 1; i <= m; ++i)
        dp[i] = dp[i - 1] + (ll)(czy[i]) * (ll)cst2[i];
    E(0);
    for(int i = 1; i <= n; ++i)
    {
        /*cout << "DP: " << i << "\n";
        for(int j = 0; j <= m; ++j)
            cout << dp[j] << " ";
        cout << "\n";*/
        int a = (upper_bound(sum2, sum2 + 1 + m, lim1[i] - sum1[i]) - sum2) - 1;
        //cout << "F1: " << i << " " << a << "\n";
        if(a < 0)
            {E(i); continue;}
        for(int j = 0; j <= a; ++j)
            dp[j] += (ll)cst1[i];
        ll cur = dp[0];
        for(int j = 1; j <= m; ++j)
        {
            cur += (ll)(czy[j]) * (ll)cst2[j];
            cur = max(cur, dp[j]);
            dp[j] = cur;
        }
        E(i);
    }
    return dp[m];
}

void Solve()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tim1[i] >> lim1[i] >> cst1[i];
        sum1[i] = (ll)tim1[i] + sum1[i - 1];
    }
    for(int i = 1; i <= m; ++i)
    {
        cin >> tim2[i] >> lim2[i] >> cst2[i];
        sum2[i] = (ll)tim2[i] + sum2[i - 1];
    }
    for(int i = 1; i <= m; ++i)
    {
        int a = (upper_bound(sum1, sum1 + 1 + n, lim2[i] - sum2[i]) - sum1) - 1;
        if(a >= 0)
        {
            czy[i] = 1;
            kon[a].pb(i);
        }
    }
    ll ans = DoDP(n, m);
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• 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