oj.uz

Submission #145591

# Submission time Handle Problem Language Result Execution time Memory
145591 2019-08-20T13:05:43 Z mat_v Watching (JOI13_watching) C++14
100 / 100
 162 ms 16120 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 760 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8440 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 126 ms 16120 KB Output is correct
4 Correct 19 ms 8952 KB Output is correct
5 Correct 162 ms 16120 KB Output is correct
6 Correct 161 ms 16012 KB Output is correct
7 Correct 11 ms 8440 KB Output is correct
8 Correct 75 ms 14324 KB Output is correct
9 Correct 20 ms 9336 KB Output is correct
10 Correct 17 ms 9116 KB Output is correct
11 Correct 156 ms 15992 KB Output is correct
12 Correct 90 ms 16120 KB Output is correct
13 Correct 11 ms 8440 KB Output is correct
14 Correct 11 ms 8440 KB Output is correct
15 Correct 11 ms 8568 KB Output is correct