oj.uz

Submission #200039

# Submission time Handle Problem Language Result Execution time Memory
200039 2020-02-05T03:47:56 Z arnold518 Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 14436 KB 
#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]), A[i]+=A[i-1];
	for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[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;

	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({X[i], i});
	sort(V.begin(), V.end());
	
	for(j=1; j<=N; j++) if(0<=X[j]) dp[j]=max(dp[j], dp[j-1]+1);
	//for(j=0; j<=N; j++) printf("%lld ", dp[j]); printf("\n");
	for(i=1; i<=M; i++)
	{
		for(j=0; j<=Y[i]; j++) dp[j]++;
		//for(j=0; j<=N; j++) printf("%lld ", dp[j]); printf("\n");
		for(j=1; j<=N; j++) if(i<=X[j]) dp[j]=max(dp[j], dp[j-1]+1);
	}
/*
	for(i=1; i<=N; i++) if(X[i]>=0) slope[i]=1, chk[i]=true;
	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);
	}
	for(i=1; i<=N; i++) slope[i]+=slope[i-1];
	printf("%lld", slope[N]+cut);
	*/
	printf("%lld\n", dp[N]);
}

Compilation message

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:64: 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]), A[i]+=A[i-1];
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
dishes.cpp:23:64: 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]), B[i]+=B[i-1];
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 372 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10079 ms 14436 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 10079 ms 14436 KB Time limit exceeded
2 Halted 0 ms 0 KB -