제출 #909841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
909841		raphaelp	구경하기 (JOI13_watching)	C++14	100 / 100	542 ms	16492 KiB

watching

#include <bits/stdc++.h>
using namespace std;
int find(int x, vector<int> &Tab, int L, int R)
{
    int m = (L + R) / 2;
    if (R == L)
        return m;
    if (Tab[m] > x)
        return find(x, Tab, L, m);
    else
        return find(x, Tab, m + 1, R);
}
int main()
{
    int N, P, Q;
    cin >> N >> P >> Q;
    P = min(N, P);
    Q = min(N, Q);
    vector<int> Tab(N);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
    }
    sort(Tab.begin(), Tab.end());
    int L = 1, R = 1000000000;
    for (int dico = 0; dico < 30; dico++)
    {
        int m = (L + R) / 2;
        vector<int> small(N), big(N);
        for (int i = 0; i < N; i++)
        {
            small[i] = find(Tab[i] + m - 1, Tab, 0, N);
            big[i] = find(Tab[i] + 2 * m - 1, Tab, 0, N);
        }
        vector<vector<int>> dp(N + 1, vector<int>(P + 1, -1));
        dp[0][0] = Q;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j <= P; j++)
            {
                if (j != P)
                    dp[small[i]][j + 1] = max(dp[i][j], dp[small[i]][j + 1]);
                if (dp[i][j] != 0)
                    dp[big[i]][j] = max(dp[i][j] - 1, dp[big[i]][j]);
            }
        }
        bool b = 0;
        for (int i = 0; i <= P; i++)
        {
            if (dp[N][i] >= 0)
                b = 1;
        }
        if (b)
            R = m;
        else
            L = m + 1;
    }
    cout << L;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50