oj.uz

Submission #200135

# Submission time Handle Problem Language Result Execution time Memory
200135 2020-02-05T13:24:50 Z arnold518 Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 19932 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 ans;

struct Point
{
	int x, y; ll val;
	bool operator < (const Point &p)
	{
		if(x==p.x) return y>p.y;
		return x<p.x;
	}
};
vector<Point> V;

ll C[MAXN+10], D[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(i=1; i<=N; i++) ans+=P[i];
	for(i=1; i<=N; i++) if(X[i]+1<=M) V.push_back({i-1, X[i]+1, -P[i]});
	for(i=1; i<=M; i++) if(Y[i]>=0) V.push_back({Y[i], i, Q[i]});

	sort(V.begin(), V.end());

	for(j=0; j<V.size(); j++)
	{
		if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
		Point it=V[j];
		//printf("%d %d %lld\n", it.x, it.y, it.val);
		for(i=1; i<=M; i++) D[i]=max(D[i-1], C[i]);
		for(i=it.y; i<=M; i++) C[i]=D[i]+it.val;
		//for(i=1; i<=M; i++) printf("%lld ", C[i]); printf("\n");
	}
	printf("%lld\n", ans+C[M]);
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(j=0; j<V.size(); j++)
           ~^~~~~~~~~
dishes.cpp:51:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j+1<V.size() && V[j].x==V[j+1].x && V[j].y==V[j+1].y) { V[j+1].val+=V[j].val; continue; }
      ~~~^~~~~~~~~
dishes.cpp:31:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
dishes.cpp:33: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:34: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:35: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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10043 ms 19932 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 Incorrect 5 ms 376 KB Output isn't correct
3 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 Incorrect 5 ms 376 KB Output isn't correct
3 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 Incorrect 5 ms 376 KB Output isn't correct
3 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 Incorrect 5 ms 376 KB Output isn't correct
3 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 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

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