Submission #145591

#	Time	Username	Problem	Language	Result	Execution time	Memory
145591		mat_v	Watching (JOI13_watching)	C++14	100 / 100	162 ms	16120 KiB

watching

#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))


using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

int n,p,q;
int dp[2004][2004];
int niz[2005];
bool moze(int w){
    for(int i=0; i<=2000; i++)dp[0][i] = 0;
    int cnmale = 0;
    int cnvel = 0;
    for(int i=1; i<=n; i++){
        while(niz[cnmale] <= niz[i] - w)cnmale++;
        if(cnmale != 0)cnmale--;
        while(niz[cnvel] <= niz[i] - 2*w)cnvel++;
        if(cnvel != 0)cnvel--;
        for(int j=0; j<=q; j++){
            int tr = 1e9;
            tr = dp[cnmale][j] + 1;
            if(j != 0)tr = min(tr, dp[cnvel][j - 1]);
            dp[i][j] = tr;
        }
    }
    if(dp[n][q] <= p)return 1;
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> p >> q;
    p = min(p,n);
    q = min(q,n);
    for(int i=1; i<=n; i++){
        cin >> niz[i];
    }
    sort(niz + 1, niz + n + 1);
    int l = 1;
    int r = 1e9;
    while(l < r){
        int mid = (l + r) / 2;
        if(moze(mid))r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

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