Submission #110019

#	Time	Username	Problem	Language	Result	Execution time	Memory
110019		tincamatei	Two Dishes (JOI19_dishes)	C++14	10 / 100	10063 ms	48652 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;

struct StepSet {
	int n;
	int len[1+MAX_N], art[1+MAX_N];
	long long limit[1+MAX_N];
	long long sp[1+MAX_N];

	int segLen[1+MAX_N];
} meal[2];

int binsrc(int p, long long t) {
	int st = -1, dr = meal[p].n + 1;

	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(meal[p].sp[mid] <= t)
			st = mid;
		else
			dr = mid;
	}
	return dr;
}

struct BadSegtree {
	int n;
	long long dp[1+MAX_N];
	int transition[1+MAX_N];

	void addRange(int l, int r, int val) {
		for(int i = l; i <= r; ++i)
			dp[i] += val;
	}

	void modifyTransition(int poz, int val) {
		transition[poz] = val;
	}

	void pushDp() {
		for(int i = 1; i <= n; i++)
			dp[i] = max(dp[i], dp[i - 1] + transition[i]);
	}
} sol;

vector<int> horizontalMod[1+MAX_N+1];

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	fscanf(fin, "%d%d", &meal[0].n, &meal[1].n);

	for(int p = 0; p < 2; ++p)
		for(int i = 1; i <= meal[p].n; ++i) {
			fscanf(fin, "%d%lld%d", &meal[p].len[i], &meal[p].limit[i], &meal[p].art[i]);
			meal[p].sp[i] = meal[p].sp[i - 1] + meal[p].len[i];
		}
	
	for(int p = 0; p < 2; ++p)
		for(int i = 1; i <= meal[p].n; ++i)
			meal[p].segLen[i] = binsrc(1 - p, meal[p].limit[i] - meal[p].sp[i]);
	
	sol.n = meal[0].n;
	sol.dp[0] = 0;
	for(int i = 1; i <= meal[0].n; ++i)
		if(meal[0].segLen[i] > 0) {
			sol.dp[i] = sol.dp[i - 1] + meal[0].art[i];
			sol.transition[i] = meal[0].art[i];
			horizontalMod[meal[0].segLen[i]].push_back(i);
		} else
			sol.dp[i] = sol.dp[i - 1];

	for(int i = 1; i <= meal[1].n; ++i) {
		sol.addRange(0, meal[1].segLen[i] - 1, meal[1].art[i]);
		for(auto it: horizontalMod[i])
			sol.modifyTransition(it, 0);
		sol.pushDp();
	}

	fprintf(fout, "%lld", sol.dp[meal[0].n]);
	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:60:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d", &meal[0].n, &meal[1].n);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:64:10: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    fscanf(fin, "%d%lld%d", &meal[p].len[i], &meal[p].limit[i], &meal[p].art[i]);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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