oj.uz

답안 #51472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51472 2018-06-18T03:39:41 Z atoiz 구경하기 (JOI13_watching) C++14
100 / 100
 338 ms 4476 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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