Submission #879310

#	Time	Username	Problem	Language	Result	Execution time	Memory
879310		hasan2006	Watching (JOI13_watching)	C++17	100 / 100	634 ms	31944 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2000 + 9 , mod = 1e9 + 7;
ll   a[N] = {}, b[N] , c[N] , d[N] , dp[N][N];

void solve()
{
    ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>x>>y;
    for(i = 1; i <= n; i++){
        cin>>a[i];
    }
    sort(a + 1 , a + n + 1);
    l = 1 , r = 1e9;
    x = min(x , n), y = min(y , n);
    while(l != r){
        m = (l + r) / 2;
        ll l1 = 1 , r1 = 1;
        for(i = 1; i <= n; i++){
            l1 = max(l1 , i);
            r1 = max(r1 , i);
            while(l1 < n && a[l1 + 1] - a[i] + 1 <= m)
                l1++;
            while(r1 < n && a[r1 + 1] - a[i] + 1 <= 2 * m)
                r1++;
            b[i] = l1;
            c[i] = r1;
        }
        for(i = 0; i <= x; i++)
            for(j = 0; j <= y; j++)
                dp[i][j] = 0;
        for(i = 0; i <= x; i++){
            for(j = 0; j <= y; j++){
                if(i)
                    dp[i][j] = max(dp[i][j] , dp[i - 1][j]) , dp[i][j] = max(dp[i][j] , b[dp[i - 1][j]  + 1]);
                if(j)
                    dp[i][j] = max(dp[i][j] , dp[i][j - 1]), dp[i][j] = max(dp[i][j] , c[dp[i][j - 1]  + 1]);
            }
        }
        if(dp[x][y] == n)
            r = m;
        else
            l = m + 1;
    }
    cout<<l<<"\n";
}

int main(){
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

Compilation message (stderr)

watching.cpp: In function 'void solve()':
watching.cpp:26:8: warning: unused variable 'q' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
watching.cpp:26:26: warning: unused variable 'z' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
watching.cpp:26:29: warning: unused variable 's' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
watching.cpp:26:37: warning: unused variable 'f' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
watching.cpp:26:48: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                ^
watching.cpp:26:60: warning: unused variable 'mn' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                            ^~
watching.cpp:26:73: warning: unused variable 'mx' [-Wunused-variable]
   26 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                         ^~

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