Submission #136522

#	Time	Username	Problem	Language	Result	Execution time	Memory
136522		TadijaSebez	Two Dishes (JOI19_dishes)	C++11	0 / 100	10010 ms	40604 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1000050;
const int M=2*N;
const ll inf=1e18;
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<ll,ll>> Qs[N];
struct BruteForce
{
	ll a[N];
	int n;
	BruteForce(){}
	void init(int _n){ n=_n;for(int i=1;i<=n;i++) a[i]=0;}
	void Add(int qs, int qe, ll f){ for(int i=qs;i<=qe;i++) a[i]+=f;}
	void Set(int qs, int qe, ll x){ for(int i=qs;i<=qe;i++) a[i]=max(a[i],x);}
	ll Get(int qi){ return a[qi];}
} STB;
int main()
{
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
	for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
	ll sum=0;
	STB.init(m);
	for(int i=1;i<=m;i++)
	{
		t[i]=upper_bound(a,a+1+n,t[i]-b[i])-a;
		if(t[i])
		{
			sum+=q[i];
			Qs[t[i]].pb({i,-q[i]});
		}
	}
	for(int i=1;i<=n;i++)
	{
		s[i]=upper_bound(b,b+1+m,s[i]-a[i])-b;
		if(s[i]) Qs[i].pb({s[i],p[i]});
		sort(Qs[i].rbegin(),Qs[i].rend());
		for(auto qu:Qs[i])
		{
			int p=qu.first-1;
			ll f=qu.second;
			STB.Add(0,p,f);
			ll g=STB.Get(p);
			STB.Set(p-1,m,g);
		}
	}
	printf("%lld\n",STB.Get(m)+sum);
	return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:24:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
dishes.cpp:25:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• 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