Submission #51472

#	Time	Username	Problem	Language	Result	Execution time	Memory
51472		atoiz	Watching (JOI13_watching)	C++14	100 / 100	338 ms	4476 KiB

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 / 50
• Subtask 2: 50 / 50