oj.uz

Submission #56532

# Submission time Handle Problem Language Result Execution time Memory
56532 2018-07-11T15:09:51 Z luciocf Watching (JOI13_watching) C++14
50 / 100
 1000 ms 32852 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2010;

typedef long long ll;

ll n, p, q;
ll num[MAXN];
ll dp[MAXN][MAXN];

ll busca2(ll k)
{
    if (k > num[n]) return n;

    ll ini = 1LL, fim = n, ans;
    while (ini <= fim)
    {
        int mid = (ini+fim)>>1;

        if (num[mid] <= k) ans = mid, ini = mid+1;
        else fim = mid-1;
    }
    return ans;
}


bool ok(ll w)
{
    memset(dp, 0LL, sizeof dp);
    for (int i = 1; i <= p; i++)
        for (int j = 1; j <= q; j++)
            dp[i][j] = 1LL;

    for (int i = 0; i <= p; i++)
    {
        for (int j = 0; j <= q; j++)
        {
            if (i)
                dp[i][j] = max(dp[i][j], busca2(num[min(n, dp[i-1][j]+1)]+w-1LL));
            if (j)
                dp[i][j] = max(dp[i][j], busca2(num[min(n, dp[i][j-1]+1)]+2LL*w-1LL));
        }
    }
    return (dp[p][q] >= n);
}

ll busca(void)
{
    ll ini = 1, fim = 1e9+10, ans;
    while (ini <= fim)
    {
        ll mid = (ini+fim)>>1;

        if (ok(mid)) ans = mid, fim = mid-1;
        else ini = mid+1;
    }
    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> p >> q;

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

    if (p+q >= n)
    {
        cout << "1\n";
        return 0;
    }

    sort(num+1, num+n+1);
    cout << busca() << "\n";
}

Compilation message

watching.cpp: In function 'll busca2(ll)':
watching.cpp:17:28: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll ini = 1LL, fim = n, ans;
                            ^~~
watching.cpp: In function 'bool ok(ll)':
watching.cpp:17:28: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
watching.cpp:17:28: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
watching.cpp: In function 'll busca()':
watching.cpp:59:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 32248 KB Output is correct
2 Correct 3 ms 32248 KB Output is correct
3 Correct 248 ms 32368 KB Output is correct
4 Correct 3 ms 32368 KB Output is correct
5 Correct 2 ms 32368 KB Output is correct
6 Correct 2 ms 32368 KB Output is correct
7 Correct 287 ms 32424 KB Output is correct
8 Correct 278 ms 32532 KB Output is correct
9 Correct 277 ms 32600 KB Output is correct
10 Correct 198 ms 32600 KB Output is correct
11 Correct 189 ms 32600 KB Output is correct
12 Correct 196 ms 32600 KB Output is correct
13 Correct 186 ms 32600 KB Output is correct
14 Correct 246 ms 32600 KB Output is correct
15 Correct 285 ms 32600 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 32600 KB Output is correct
2 Correct 3 ms 32600 KB Output is correct
3 Correct 4 ms 32600 KB Output is correct
4 Correct 3 ms 32600 KB Output is correct
5 Correct 4 ms 32600 KB Output is correct
6 Correct 3 ms 32600 KB Output is correct
7 Correct 295 ms 32744 KB Output is correct
8 Correct 541 ms 32852 KB Output is correct
9 Correct 481 ms 32852 KB Output is correct
10 Correct 415 ms 32852 KB Output is correct
11 Correct 623 ms 32852 KB Output is correct
12 Execution timed out 1044 ms 32852 KB Time limit exceeded
13 Halted 0 ms 0 KB -