oj.uz

Submission #37766

# Submission time Handle Problem Language Result Execution time Memory
37766 2017-12-28T05:12:07 Z MatheusLealV Watching (JOI13_watching) C++14
100 / 100
 473 ms 18624 KB 
#include <bits/stdc++.h>
#define N 2050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, p, q, v[N], dp[N][N], prox[N][3], A, B;

int prox_(int i, int w)
{
    int ini = i, fim = n, mid, best;

    while(fim >= ini)
    {
        mid = (ini + fim)/2;

        if(v[mid] - v[i] + 1 <= w) best = mid, ini = mid + 1;

        else fim = mid - 1;
    }

    return best + 1;
}

int solve(int p, int q)
{
    if(!p && !q) return 1;

    if(dp[p][q] != -1) return dp[p][q];

    int ans = 1;

    if(p) ans = prox[ solve(p - 1, q) ][1];

    if(q) ans = max(ans, prox[solve(p, q - 1)][2]);

    return dp[p][q] = ans;
}

int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>A>>B;

    for(int i = 1; i <= n; i++) cin>>v[i];

    if(A + B >= n)
    {
        cout<<"1\n";

        return 0;
    }

    sort(v + 1, v + n + 1);
    
    int ini = 1, fim = 1e9, mid, best = -1;

    while(fim >= ini)
    {
        mid = (ini + fim)/2;

        memset(dp, -1, sizeof dp);
        
        for(int i = 1; i <= n; i++) prox[i][1] = prox_(i, mid), prox[i][2] = prox_(i, 2*mid);

        prox[n + 1][1] = n + 1, prox[n + 1][2] = n + 1;

        if(solve(A, B) > n) best = mid, fim = mid - 1;

        else ini = mid + 1;
    }

    cout<<best<<'\n';
}

Compilation message

watching.cpp: In function 'int prox_(int, int)':
watching.cpp:23:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return best + 1;
                   ^
watching.cpp: In function 'int32_t main()':
watching.cpp:23:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
watching.cpp:12:32: note: 'best' was declared here
     int ini = i, fim = n, mid, best;
                                ^
watching.cpp:23:19: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return best + 1;
                   ^
watching.cpp:12:32: note: 'best' was declared here
     int ini = i, fim = n, mid, best;
                                ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 113 ms 18624 KB Output is correct
4 Correct 0 ms 18624 KB Output is correct
5 Correct 0 ms 18624 KB Output is correct
6 Correct 0 ms 18624 KB Output is correct
7 Correct 63 ms 18624 KB Output is correct
8 Correct 63 ms 18624 KB Output is correct
9 Correct 123 ms 18624 KB Output is correct
10 Correct 83 ms 18624 KB Output is correct
11 Correct 109 ms 18624 KB Output is correct
12 Correct 79 ms 18624 KB Output is correct
13 Correct 86 ms 18624 KB Output is correct
14 Correct 69 ms 18624 KB Output is correct
15 Correct 69 ms 18624 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 0 ms 18624 KB Output is correct
4 Correct 0 ms 18624 KB Output is correct
5 Correct 0 ms 18624 KB Output is correct
6 Correct 0 ms 18624 KB Output is correct
7 Correct 69 ms 18624 KB Output is correct
8 Correct 129 ms 18624 KB Output is correct
9 Correct 139 ms 18624 KB Output is correct
10 Correct 193 ms 18624 KB Output is correct
11 Correct 176 ms 18624 KB Output is correct
12 Correct 473 ms 18624 KB Output is correct
13 Correct 89 ms 18624 KB Output is correct
14 Correct 106 ms 18624 KB Output is correct
15 Correct 86 ms 18624 KB Output is correct