oj.uz

Submission #136522

# Submission time Handle Problem Language Result Execution time Memory
136522 2019-07-25T12:21:24 Z TadijaSebez Two Dishes (JOI19_dishes) C++11
0 / 100
 10000 ms 40604 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10010 ms 40604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10010 ms 40604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10010 ms 40604 KB Time limit exceeded
2 Halted 0 ms 0 KB -