Submission #125990

#	Time	Username	Problem	Language	Result	Execution time	Memory
125990		MvC	Two Dishes (JOI19_dishes)	C++11	0 / 100	419 ms	42072 KiB

dishes

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int i,j,n,m;
ll st[4*nmax],a[nmax],b[nmax],s[nmax],q[nmax],p[nmax],t[nmax],ans,x;
map<pair<int,int>,ll>mp;
map<pair<int,int>,ll>::iterator it;
pair<pair<int,int>,ll>pr;
void upd(int nod,int l,int r,int p,ll v)
{
	if(l==r)
	{
		st[nod]=max(st[nod],v);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid)upd(2*nod,l,mid,p,v);
	else upd(2*nod+1,mid+1,r,p,v);
	st[nod]=max(st[2*nod],st[2*nod+1]);
}
ll qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return 0;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	return max(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i]>>s[i]>>p[i];
		a[i]+=a[i-1];
	}
	for(i=1;i<=m;i++)
	{
		cin>>b[i]>>t[i]>>q[i];
		b[i]+=b[i-1];
	}
	for(i=1;i<=n;i++)
	{
		if(a[i]>s[i])continue;
		if(a[i]+b[m]<=s[i])
		{
			ans+=p[i];
			continue;
		}
		j=upper_bound(b+1,b+m+1,s[i]-a[i])-(b+1);
		if(!j)continue;
		//cout<<i<<" "<<j<<" "<<p[i]<<endl;
		mp[mkp(i,j)]+=p[i];
	}
	for(i=1;i<=m;i++)
	{
		if(b[i]>t[i])continue;
		if(b[i]+a[n]<=t[i])
		{
			ans+=q[i];
			continue;
		}
		j=upper_bound(a+1,a+n+1,t[i]-b[i])-(a+1);
		if(!j)continue;
		//cout<<j<<" "<<i<<" "<<q[i];
		mp[mkp(j,i)]+=q[i];
	}
	for(it=mp.begin();it!=mp.end();it++)
	{
		pr=(*it);
		//cout<<pr.fr.fr<<" "<<pr.fr.sc<<" "<<pr.sc<<endl;
		x=qry(1,1,m,1,pr.fr.sc);
		upd(1,1,m,pr.fr.sc,x+pr.sc);
	}
	cout<<ans+qry(1,1,m,1,m)<<endl;
    return 0;
}

Compilation message (stderr)

dishes.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
dishes.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

• 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