Submission #963891

#	Time	Username	Problem	Language	Result	Execution time	Memory
963891		Tuanlinh123	Two Dishes (JOI19_dishes)	C++17	0 / 100	1 ms	460 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;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, sum=0; cin >> n >> m;
    if (n>2000) exit(0);
    vector <ll> a(n), s(n), p(n), b(m), t(m), q(m);
    vector <vector <pll>> H(n);
    for (ll i=0; i<n; i++) cin >> a[i] >> s[i] >> p[i];
    for (ll j=0; j<m; j++) cin >> b[j] >> t[j] >> q[j];
    for (ll i=1; i<n; i++) a[i]+=a[i-1];
    for (ll i=1; i<m; i++) b[i]+=b[i-1];
    for (ll i=0; i<n; i++)
    {
        if (s[i]-a[i]<0) continue; sum+=p[i];
        ll pos=lower_bound(b.begin(), b.end(), s[i]-a[i]+1)-b.begin();
        if (pos<m) H[i].pb({pos+1, -p[i]});
    }
    for (ll i=0; i<m; i++)
    {
        if (t[i]-b[i]<0) continue;
        ll pos=lower_bound(a.begin(), a.end(), t[i]-b[i]+1)-a.begin();
        if (pos<n) H[pos].pb({i+1, q[i]});
    }
    vector <ll> ans(m+1, sum);
    for (ll i=0; i<n; i++)
    {
        sort(H[i].begin(), H[i].end());
        for (ll j=0, sum=0, ptr=0; j<=m; j++)
        {
            while (ptr<sz(H[i]) && H[i][ptr].fi<=j)
                sum+=H[i][ptr].se, ptr++;
            if (j) ans[j]=max(ans[j-1], ans[j]+sum);
        }
    }
    cout << ans[m];
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:26:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |         if (s[i]-a[i]<0) continue; sum+=p[i];
      |         ^~
dishes.cpp:26:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |         if (s[i]-a[i]<0) continue; sum+=p[i];
      |                                    ^~~

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