Submission #389662

#	Time	Username	Problem	Language	Result	Execution time	Memory
389662		denkendoemeer	Two Dishes (JOI19_dishes)	C++14	100 / 100	3271 ms	250168 KiB

dishes

#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
using namespace std;
ll n,m,ans,a[1000005],b[1000005],s[1000005],t[1000005],p[1000005],q[1000005],suma[1000005],sumb[1000005],d[1000005],lim[1000005];
vector<int>v[1000005],aux;
set<int>st;
void update(int poz)
{
    ll num=0;
    while(poz<=m){
        int nex=*st.upper_bound(poz);
        if (d[poz]-num>lim[poz]){
            d[poz]-=num;
            break;
        }
        num+=lim[poz]-d[poz];
        d[poz]=lim[poz];
        st.erase(poz);
        poz=nex;
    }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld",&n,&m);
    int i;
    for(i=1;i<=n;i++){
        scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
        suma[i]=suma[i-1]+a[i];
    }
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&b[i],&t[i],&q[i]);
        sumb[i]=sumb[i-1]+b[i];
        if (sumb[i]>t[i])
            continue;
        d[i]=lim[i]=q[i];
        int auxi=upper_bound(suma,suma+n+1,t[i]-sumb[i])-suma;
        v[auxi].push_back(i);
    }
    st.insert(m+1);
    for(i=1;i<=n;i++){
        aux.clear();
        if (suma[i]<=s[i]){
            int auxi=upper_bound(sumb,sumb+m+1,s[i]-suma[i])-sumb-1;
            d[0]+=p[i];
            d[auxi+1]-=p[i];
            st.insert(auxi+1);
            aux.push_back(auxi+1);
        }
        for(auto it:v[i]){
            lim[it]=0;
            st.insert(it);
            aux.push_back(it);
        }
        for(auto it:aux)
            update(it);
    }
    for(i=0;i<=m;i++)
        ans+=d[i];
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%lld%lld%lld",&a[i],&s[i],&p[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%lld%lld%lld",&b[i],&t[i],&q[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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