oj.uz

Submission #1084029

# Submission time Handle Problem Language Result Execution time Memory
1084029 2024-09-04T21:13:29 Z MrPavlito Watching (JOI13_watching) C++17
100 / 100
 277 ms 16220 KB 
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 2e3+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

int n,p,q;
vector<int> niz;
int dp[MAXN][MAXN];

bool solve(int mid)
{
    memset(dp, -1, sizeof(dp));
    for(int i=0; i<=p; i++)
    {
        for(int j=0; j<=q; j++)
        {
            if(i==0 && j == 0)continue;
            else if(i==0)
            {
                int index = dp[i][j-1]+1;
                int tr = niz[index] + mid+mid-1;
                int poz = upper_bound(all(niz), tr) - niz.begin()-1;
                dp[i][j] = poz;
            }
            else if(j == 0)
            {
                int index = dp[i-1][j]+1;
                int tr = niz[index] +mid-1;
                int poz = upper_bound(all(niz), tr) - niz.begin()-1;
                dp[i][j] = poz;
            }
            else
            {
                int index1 = dp[i][j-1]+1;
                int tr = niz[index1] + mid+mid-1;
                int poz = upper_bound(all(niz), tr) - niz.begin()-1;
                int index2 = dp[i-1][j]+1;
                int tr2 = niz[index2] + mid-1;
                int poz2 = upper_bound(all(niz), tr2) - niz.begin()-1;
                dp[i][j] = max(poz, poz2);
            }
            //cout << dp[i][j] << " ";
            if(dp[i][j]>=n-1)return 1;
        }
        //cout << endl;
    }
    return 0;

}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n >> p >> q;
        niz.resize(n);
        p = min(p,n);
        q = min(q,n);
        for(int i=0; i<n; i++)cin >> niz[i];
        sort(all(niz));
        int l = 1; int r = 1e9+1;
        int rez = r;
        if(p+q>= n)
        {
            cout << 1 << endl;
            return 0;
        }
        while(l<=r)
        {
            int mid = l+r>>1;
            if(solve(mid))
            {
                rez = mid;
                r = mid-1;
            }
            else l = mid+1;
        }
        cout << rez << endl;
    }
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:84:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |             int mid = l+r>>1;
      |                       ~^~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15960 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 20 ms 15964 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 19 ms 16196 KB Output is correct
8 Correct 18 ms 16188 KB Output is correct
9 Correct 18 ms 15964 KB Output is correct
10 Correct 18 ms 16192 KB Output is correct
11 Correct 18 ms 15964 KB Output is correct
12 Correct 17 ms 15964 KB Output is correct
13 Correct 19 ms 16076 KB Output is correct
14 Correct 18 ms 15964 KB Output is correct
15 Correct 17 ms 15960 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15964 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 492 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 19 ms 16216 KB Output is correct
8 Correct 55 ms 16196 KB Output is correct
9 Correct 67 ms 15960 KB Output is correct
10 Correct 84 ms 16196 KB Output is correct
11 Correct 75 ms 16216 KB Output is correct
12 Correct 277 ms 16216 KB Output is correct
13 Correct 20 ms 16220 KB Output is correct
14 Correct 18 ms 15988 KB Output is correct
15 Correct 17 ms 15964 KB Output is correct