Submission #1207528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207528		diana	Watching (JOI13_watching)	C++20	100 / 100	801 ms	16336 KiB

watching

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

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

bool check(int w)
{
    int dp[M][M];
    for(int i=0; i<M; i++)
        for(int j=0; j<M; j++)
            dp[i][j] = 0;

    bool ret = 0;
    int beigas = *s.rbegin();

    for(int i=0; i<=p && i<M && !ret; i++)
    {
        for(int j=0; j<=q && i+j<M && !ret; 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[i][j] >= beigas)
                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;
    M = n + 10;
    for(int i=0; i<n; i++)
    {
        int a; cin >> a;
        s.insert(a);
    }
    cout << binary();

    return 0;
}

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