oj.uz

Submission #105845

# Submission time Handle Problem Language Result Execution time Memory
105845 2019-04-15T10:35:40 Z Pro_ktmr Two Dishes (JOI19_dishes) C++14
0 / 100
 3 ms 512 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

int N,M;
LL A[1000000],B[1000000],S[1000000],T[1000000],P[1000000],Q[1000000],yoyuA[1000000],yoyuB[1000000];
LL waA[1000000],waB[1000000];

LL dp[2001][2001];
LL solve(int i, int j){
	if(dp[i][j] != LLONG_MIN) return dp[i][j];
	if(i < N && j < M){
		dp[i][j] = solve(i+1, j);
		if(S[i] >= (j==0 ? 0 : waB[j-1]) + waA[i]) dp[i][j] += P[i];
		LL tmp = solve(i, j+1);
		if(T[j] >= (i==0 ? 0 : waA[i-1]) + waB[j]) tmp += Q[j];
		dp[i][j] = max(dp[i][j], tmp);
	}
	else if(i < N){
		dp[i][j] = solve(i+1, j);
		if(S[i] >= (j==0 ? 0 : waB[j-1]) + waA[i]) dp[i][j] += P[i];
	}
	else if(j < M){
		dp[i][j] = solve(i, j+1);
		if(T[j] >= (i==0 ? 0 : waA[i-1]) + waB[j]) dp[i][j] += Q[j];
	}
	else dp[i][j] = 0;
	return dp[i][j];
}

void gyaku(int i, int j){
	cout << i << " " << j << endl;
	if(i < N && j < M){
		LL tmp = solve(i, j+1);
		if(T[j] >= (i==0 ? 0 : waA[i-1]) + waB[j]) tmp += Q[j];
		if(dp[i][j] == tmp) gyaku(i, j+1);
		else gyaku(i+1, j);
	}
	else if(i < N){
		gyaku(i+1, j);
	}
	else if(j < M){
		gyaku(i, j+1);
	}
}

int main(){
	scanf("%d%d", &N, &M);
	if(N > 2000 || M > 2000) return -1;
	for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
	for(int i=0; i<M; i++) scanf("%lld%lld%lld", B+i, T+i, Q+i);
	
	//
	
	for(int i=0; i<N; i++) waA[i] = (i==0 ? 0 : waA[i-1]) + A[i];
	for(int i=0; i<M; i++) waB[i] = (i==0 ? 0 : waB[i-1]) + B[i];
	for(int i=0; i<=N; i++){
		for(int j=0; j<=M; j++){
			dp[i][j] = LLONG_MIN;
		}
	}
	
	cout << solve(1,0)+58 << endl;
	
	for(int i=0; i<=N; i++){
		for(int j=0; j<=M; j++){
			cout << solve(i, j) << "\t";
		}
		cout << endl;
	}
	gyaku(1,0);
	
	return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:50: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:52:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%lld%lld%lld", A+i, S+i, P+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; 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 Runtime error 3 ms 384 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 384 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 384 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -