Submission #1207517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207517		diana	Watching (JOI13_watching)	C++20	0 / 100	446 ms	327680 KiB

watching

#include <bits/stdc++.h>
using namespace std;

const int R = 1e9;
int n, p, q;
set<int> s;

bool check(int w)
{
    int dp[p+1][q+1];
    for(int i=0; i<=p; i++)
        for(int j=0; j<=q; j++)
            dp[i][j] = 0;
    bool ret = 0;
    dp[0][0] = 0;

    for(int i=0; i<=p && !ret; i++)
    {
        for(int j=0; j<=q && !ret && i+j<=n; j++)
        {
            if(i > 0)
            {
                auto t = s.lower_bound(dp[i-1][j]+1);
                if(t == s.end())
                    ret = 1;
                else
                    dp[i][j] = max(dp[i][j], (*t)+w-1);
            }
            if(j > 0)
            {
                auto t = s.lower_bound(dp[i][j-1]+1);
                if(t == s.end())
                    ret = 1;
                else
                    dp[i][j] = max(dp[i][j], (*t)+2*w-1);
            }
        }
    }
    if(dp[p][q] >= *s.rbegin())
        ret = 1;

    return ret;
}

int binary()
{
    int l = 1, r = R;
    while(l < r)
    {
        int m = (l+r)/2;
        if(check(m))
            r = m;
        else
            l = m+1;
    }
    return l;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> p >> q;

    for(int i=0; i<n; i++)
    {
        int a; cin >> a;
        s.insert(a);
    }
    cout << binary();

    return 0;
}

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