Submission #51472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51472	2018-06-18T03:39:41 Z	atoiz	Watching (JOI13_watching)	C++14	100 / 100	338 ms	4476 KB

watching

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>

using namespace std;

int eventsNo, smallNo, largeNo;
vector<int> events;
vector< vector<int> > dp;

bool works(int width)
{

	dp.assign(smallNo + 1, vector<int>(largeNo + 1, -1));

	for (int pq = 1; pq <= largeNo + smallNo; ++pq) {
		for (int p = 0; p <= smallNo; ++p) {
			int q = pq - p;
			if (q < 0 || q > largeNo) continue;

            if (p > 0) {
				int firstIdx = dp[p-1][q] + 1;
				int firstEvent = events[firstIdx];
				int lastIdx = firstIdx;
				while (lastIdx + 1 < eventsNo && (events[lastIdx + 1] <= firstEvent + width - 1)) ++lastIdx;
				dp[p][q] = min(lastIdx, eventsNo - 1);
//				cerr << width << ", dp[" << p << "][" << q << "]: " << firstIdx << " " << lastIdx << endl;
//
            }

            if (q > 0) {
				int firstIdx = dp[p][q-1] + 1;
				int firstEvent = events[firstIdx];
				int lastIdx = firstIdx;
				while (lastIdx + 1< eventsNo && events[lastIdx + 1] <= firstEvent + 2*width - 1) ++lastIdx;
				dp[p][q] = max(dp[p][q], min(lastIdx, eventsNo - 1));
            }

//			cerr << width << ", dp[" << p << "][" << q << "]: " << dp[p][q] << endl;
		}
	}

	return dp[smallNo][largeNo] == eventsNo - 1;
}

int binarySearch()
{
	int left = 0, right = 1e9 + 7;
	while (true) {
//		cerr << left << ' ' << right << endl;
		if (right - left <= 3) {
			while (!works(left)) ++left;
			return left;
		}

		int mid = left + (right - left) / 2;
		if (works(mid)) right = mid;
		else left = mid + 1;
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie();
    cin >> eventsNo >> smallNo >> largeNo;
    events.assign(eventsNo, 0);
    for (int i = 0; i < eventsNo; ++i) {
		cin >> events[i];
    }
    sort(events.begin(), events.end());

    if (smallNo + largeNo >= eventsNo) {
		cout << 1 << endl;
		return 0;
    }

//	cout << works(4) << endl;
    cout << binarySearch() << endl;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	3 ms	428 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	2 ms	508 KB	Output is correct
8	Correct	2 ms	764 KB	Output is correct
9	Correct	2 ms	764 KB	Output is correct
10	Correct	3 ms	764 KB	Output is correct
11	Correct	3 ms	764 KB	Output is correct
12	Correct	2 ms	764 KB	Output is correct
13	Correct	2 ms	764 KB	Output is correct
14	Correct	2 ms	764 KB	Output is correct
15	Correct	2 ms	764 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	764 KB	Output is correct
2	Correct	2 ms	764 KB	Output is correct
3	Correct	2 ms	764 KB	Output is correct
4	Correct	3 ms	764 KB	Output is correct
5	Correct	2 ms	764 KB	Output is correct
6	Correct	3 ms	764 KB	Output is correct
7	Correct	3 ms	764 KB	Output is correct
8	Correct	35 ms	1008 KB	Output is correct
9	Correct	49 ms	1128 KB	Output is correct
10	Correct	166 ms	1384 KB	Output is correct
11	Correct	43 ms	1384 KB	Output is correct
12	Correct	338 ms	4476 KB	Output is correct
13	Correct	3 ms	4476 KB	Output is correct
14	Correct	3 ms	4476 KB	Output is correct
15	Correct	4 ms	4476 KB	Output is correct