Submission #105845

#	Time	Username	Problem	Language	Result	Execution time	Memory
105845		Pro_ktmr	Two Dishes (JOI19_dishes)	C++14	0 / 100	3 ms	512 KiB

dishes

#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 (stderr)

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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9