oj.uz

Submission #259122

# Submission time Handle Problem Language Result Execution time Memory
259122 2020-08-07T08:29:26 Z patrikpavic2 Two Dishes (JOI19_dishes) C++17
10 / 100
 232 ms 49088 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define PB push_back

using namespace std;

typedef long long ll;

const int N = 2e3 + 50;
const ll INF = 1e18;

ll del[N],  mora[N], dp[N][N], S[N], T[N];
int n, m, bio[N][N];
int Q[N], P[N], A[N], B[N];
int SS[N], TT[N];
vector < ll > v, v2;
vector < int > brisi[N];

ll f(int x, int y){
	if(x > n || y > m) return -INF;
	if(x == n && y == m) return 0;
	if(bio[x][y]) return dp[x][y];
	dp[x][y] = max(f(x + 1, y) + (SS[x + 1] >= y ? P[x + 1] : 0), f(x, y + 1) + (TT[y + 1] >= x ? Q[y + 1] : 0));
	bio[x][y] = 1;
	return dp[x][y];
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
		scanf("%d%lld%d", A + i, S + i, P + i);
	for(int i = 1;i <= m;i++)
		scanf("%d%lld%d", B + i, T + i, Q + i);
	ll cur = 0; v.PB(cur);
	for(int i = 1;i <= m;i++)
		cur += B[i], v.PB(cur);
	cur = 0; v2.PB(cur);
	for(int i = 1;i <= n;i++){
		cur += A[i]; v2.PB(cur);
		if(S[i] < cur)
			P[i] = 0, S[i] = cur;
		SS[i] = upper_bound(v.begin(), v.end(), S[i] - cur) - v.begin() - 1;
	}
	cur = 0;
	for(int i = 1;i <= m;i++){
		cur += B[i];
		if(T[i] < cur)
			Q[i] = 0, T[i] = cur;
		TT[i] = upper_bound(v2.begin(), v2.end(), T[i] - cur) - v2.begin() - 1;
	}	
	printf("%lld\n", f(0, 0));
	return 0;
	for(int i = 1;i <= m;i++){
		del[i] = Q[i], mora[i] = Q[i];
		brisi[SS[i]].PB(i);
	}
	for(int i = 1;i <= n;i++){
		del[0] += P[i];
		del[TT[i] + 1] = max(del[TT[i] + 1] - P[i], mora[TT[i] + 1]);
		for(int j : brisi[i])
			mora[j] = -INF;
	}
	ll ans = 0;
	for(int i = 0;i <= m;i++)
		ans += del[i];
	printf("%lld\n", ans);
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:32: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:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%d", A + i, S + i, P + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld%d", B + i, T + i, Q + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 210 ms 48888 KB Output is correct
18 Correct 231 ms 49016 KB Output is correct
19 Correct 217 ms 49012 KB Output is correct
20 Correct 200 ms 49088 KB Output is correct
21 Correct 221 ms 47224 KB Output is correct
22 Correct 215 ms 49016 KB Output is correct
23 Correct 209 ms 48912 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 210 ms 48888 KB Output is correct
18 Correct 231 ms 49016 KB Output is correct
19 Correct 217 ms 49012 KB Output is correct
20 Correct 200 ms 49088 KB Output is correct
21 Correct 221 ms 47224 KB Output is correct
22 Correct 215 ms 49016 KB Output is correct
23 Correct 209 ms 48912 KB Output is correct
24 Incorrect 232 ms 18024 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 210 ms 48888 KB Output is correct
18 Correct 231 ms 49016 KB Output is correct
19 Correct 217 ms 49012 KB Output is correct
20 Correct 200 ms 49088 KB Output is correct
21 Correct 221 ms 47224 KB Output is correct
22 Correct 215 ms 49016 KB Output is correct
23 Correct 209 ms 48912 KB Output is correct
24 Incorrect 232 ms 18024 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 0 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 210 ms 48888 KB Output is correct
18 Correct 231 ms 49016 KB Output is correct
19 Correct 217 ms 49012 KB Output is correct
20 Correct 200 ms 49088 KB Output is correct
21 Correct 221 ms 47224 KB Output is correct
22 Correct 215 ms 49016 KB Output is correct
23 Correct 209 ms 48912 KB Output is correct
24 Incorrect 232 ms 18024 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

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

Subtask #8
0 / 9.0

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