Submission #126729

#	Time	Username	Problem	Language	Result	Execution time	Memory
126729		dndhk	Two Dishes (JOI19_dishes)	C++14	10 / 100	218 ms	16248 KiB

dishes

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;

int N, M;
struct S{
	S(ll t, ll l, ll c) : t(t), l(l), c(c) {}
	ll t, l, c;
};
vector<S> A, B;

int dp[MAX_N+10][MAX_N+10];
ll S1[MAX_N+10], S2[MAX_N+10];

void pro1(){
	int ans = 0;
	for(int i=0; i<=N; i++){
		for(int j=0; j<=M; j++){
			if(i!=N){
				dp[i+1][j] = max(dp[i+1][j], dp[i][j] + (S1[i] + S2[j] <= A[i].l - A[i].t));
			}if(j!=M){
				dp[i][j+1] = max(dp[i][j+1], dp[i][j] + (S1[i] + S2[j] <= B[j].l - B[j].t));
			}
			ans = max(ans, dp[i][j]);
		}
	}
	cout<<ans;
}

ll C1[MAX_N+10], C2[MAX_N+10];
ll L;

void pro2(){	
	ll ans=0;
	int idx = M;
	for(int i=0; i<=N; i++){
		while(idx>0 && S2[idx] + S1[i] > L)	idx--;
		if(S2[idx] + S1[i] > L)	break;
		//cout<<C1[i]<<" "<<C2[idx]<<" "<<C1[i] + C2[idx]<<endl;
		ans = max(ans, C1[i] + C2[idx]);
	}
	cout<<ans;
}

bool tf = true;

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		ll a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		if(c!=1)	tf = false;
		L = b;
		A.pb({a, b, c});
		S1[i+1] = S1[i] + a;
		C1[i+1] = C1[i] + c;
	}
	for(int i=0; i<N; i++){
		C1[i+1] = max(C1[i], C1[i+1]);
	}
	for(int i=0; i<M; i++){
		ll a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		if(c!=1)	tf = false;
		B.pb({a, b, c});
		S2[i+1] = S2[i] + a;
		C2[i+1] = C2[i] + c;
	}
	for(int i=0; i<M; i++){
		C2[i+1] = max(C2[i], C2[i+1]);
	}
	if(N<=2000 && M<=2000 && tf){
		pro1();
	}else{
		pro2();
	}

	return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:69: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9