oj.uz

Submission #110018

# Submission time Handle Problem Language Result Execution time Memory
110018 2019-05-08T21:30:57 Z tincamatei Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 54392 KB 
#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]);
		sol.pushDp();
		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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10072 ms 54392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10072 ms 54392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10072 ms 54392 KB Time limit exceeded
2 Halted 0 ms 0 KB -