Submission #200050

#	Time	Username	Problem	Language	Result	Execution time	Memory
200050		arnold518	Two Dishes (JOI19_dishes)	C++14	10 / 100	10043 ms	14328 KiB

dishes

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, M;
ll A[MAXN+10], S[MAXN+10], P[MAXN+10];
ll B[MAXN+10], T[MAXN+10], Q[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
ll slope[MAXN+10], cut, dp[MAXN+10];
bool chk[MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
	for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);

	for(i=1; i<=N; i++) A[i]+=A[i-1];
	for(i=1; i<=M; i++) B[i]+=B[i-1];

	for(i=1; i<=N; i++) X[i]=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
	for(i=1; i<=M; i++) Y[i]=upper_bound(A, A+N+1, T[i]-B[i])-A-1;


	for(j=1; j<=N; j++)
	{
		if(0<=X[j]) dp[j]=dp[j-1]+1;
		else dp[j]=dp[j-1];
	}
	for(i=1; i<=M; i++)
	{
		for(j=0; j<=Y[i]; j++) dp[j]++;
		for(j=1; j<=N; j++)
		{
			if(i<=X[j]) dp[j]=max(dp[j], dp[j-1]+1);
			else dp[j]=max(dp[j], dp[j-1]);
		}
	}
/*
	for(j=1; j<=N; j++) if(0<=X[j]) slope[j]=1;
	for(i=1; i<=M; i++)
	{
		slope[0]++; slope[Y[i]+1]--;
		for(j=1; j<=N; j++)
		{
			if(i<=X[j]) slope[j]=max(slope[j], 1ll);
			else slope[j]=max(slope[j], 0ll);
		}
	}	
	for(i=1; i<=N; i++) slope[i]+=slope[i-1];
*/
/*
	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({X[i], i});
	sort(V.begin(), V.end());

	for(i=1; i<=N; i++) chk[i]=true;
	for(i=1; i<=N; i++) if(X[i]>=0) slope[i]=1;
	for(i=1, j=0; i<=M; i++)
	{
		for(; j<V.size() && V[j].first<i; j++) chk[V[j].second]=false;
		if(Y[i]>=0)
		{
			cut++;
			if(!chk[Y[i]+1] && slope[Y[i]+1]) slope[Y[i]+1]=0;
		}
		//for(k=1; k<=N; k++) printf("%lld ", slope[k]); printf(" : %lld\n", cut);
	}
	
*/
	printf("%lld\n", dp[N]);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:19:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
dishes.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:22:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:23:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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