Submission #1243105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243105		Bui_Quoc_Cuong	Watching (JOI13_watching)	C++20	100 / 100	97 ms	16160 KiB

watching

/* 29 . 03 . 2008 */
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> pii ;
typedef pair<ll,int> pli ;
typedef pair<int,ll> pil ;
typedef pair<ll,ll> pll ;
#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define uni(a) sort(all(a)), a.resize(unique(all(a))-a.begin())
#define MASK(a) (1ll << a)

int gcd(int x, int y) {return __gcd(x, y) ;}
int lg(int x) {return __lg(x) ;}
int lcm(int x, int y) {return x / __gcd(x, y) * y ;}

template <class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template <class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}

const int N = 2e3 + 5, M = 5e3 + 5, LG = __lg(N) + 1, base = 311 ;
const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 1e9 + 3 ;
const long long inf = 1e18 ;

int n, p, q ;
ll a[N];

void init() {
    cin >> n >> p >> q ;
    FOR(i, 1, n) cin >> a[i] ;
    sort(a + 1, a + 1 + n) ;
}

int dp[N][N] ;
// dp(i, j) : so lan dung w it de phu 1 ... i va dung j lan 2 * w

bool check(ll w) {
    FOR(i, 0, n) FOR(j, 0, min(n, q)) dp[i][j] = oo ;

    dp[0][0] = 0 ;
    dp[1][0] = 1 ;
    dp[1][1] = 0 ;

    FOR(i, 2, n) {
        int l = 1, r = i, v1 = i ;

        while(l <= r) {
            int mid = (l + r) >> 1 ;
            if(a[mid] >= a[i] - w + 1) v1 = mid, r = mid - 1 ;
            else l = mid + 1 ;
        }

        l = 1, r = i ;
        int v2 = i ;

        while(l <= r) {
            int mid = (l + r) >> 1 ;
            if(a[mid] >= a[i] - 1ll * w * 2 + 1) v2 = mid, r = mid - 1 ;
            else l = mid + 1 ;
        }
        FOR(j, 0, min(i, q)) {
            if(j > 0) mini(dp[i][j], dp[v2 - 1][j - 1]) ;
            mini(dp[i][j], dp[v1 - 1][j] + 1) ;
        }
    }

    int ans = oo ;
    FOR(j, 0, min(n, q)) mini(ans, dp[n][j]) ;
    return (ans <= p) ;
}

void solve() {
    ll l = 1, r = 1e9, ans = - 1 ;
    while(l <= r) {
        ll mid = (l + r) >> 1 ;
        if(check(mid)) ans = mid, r = mid - 1 ;
        else l = mid + 1 ;
    }
    cout << ans ;
}

signed main() {
    #define task "paint"
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
    if(fopen(".inp","r")) {
        freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
    }
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
    }
    init() ;
    solve() ;
    cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
    return 0 ;
}
/* Watbor */

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
watching.cpp:96:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:99:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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