Submission #963893

#	Time	Username	Problem	Language	Result	Execution time	Memory
963893		Tuanlinh123	Two Dishes (JOI19_dishes)	C++17	10 / 100	30 ms	31836 KiB

dishes

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=2005, inf=1e18;
ll a[maxn], s[maxn], p[maxn], b[maxn], t[maxn], q[maxn];
ll dp[maxn][maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m; cin >> n >> m;
    if (n>2000) exit(0);
    for (ll i=1; i<=n; i++) cin >> a[i] >> s[i] >> p[i], a[i]+=a[i-1];
    for (ll i=1; i<=m; i++) cin >> b[i] >> t[i] >> q[i], b[i]+=b[i-1];
    for (ll i=0; i<=n; i++)
        for (ll j=0; j<=m; j++)
            dp[i][j]=-inf;
    for (ll i=0; i<=n; i++) for (ll j=0; j<=m; j++)
    {
        if (i==0 && j==0) dp[i][j]=0;
        if (i) dp[i][j]=max(dp[i][j], dp[i-1][j]+(a[i]+b[j]<=s[i]?p[i]:0));
        if (j) dp[i][j]=max(dp[i][j], dp[i][j-1]+(a[i]+b[j]<=t[j]?q[j]:0));
    }
    cout << dp[n][m];
}

• 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