oj.uz

Submission #553961

# Submission time Handle Problem Language Result Execution time Memory
553961 2022-04-27T12:21:15 Z AA_Surely Watching (JOI13_watching) C++17
100 / 100
 138 ms 16080 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int N = 2000 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, s, b;
int ns[N], dp[N][N];

inline bool check(int w) {
    int wb = 0, w2b = 0;
    FOR(i, 1, n + 1) {
        int pl1 = lower_bound(ns + 1, ns + n + 1, ns[i] - 2 * w + 1) - ns;
        int pl2 = lower_bound(ns + 1, ns + n + 1, ns[i] - w + 1) - ns;

        dp[i][0] = dp[pl1 - 1][0] + 1;
        FOR(j, 1, n + 1) dp[i][j] = min(dp[pl1 - 1][j] + 1, dp[pl2 - 1][j - 1]);
        
    }
    
    return (dp[n][min(n, s)] <= b);
}

int main() {
    IOS;
    
    cin >> n >> s >> b;
    FOR(i, 1, n + 1) cin >> ns[i];
    ns[0] = -INF;

    sort(ns + 1, ns + n + 1);
    int l = 1, r = INF;

    while(l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l;
}

Compilation message

watching.cpp: In function 'bool check(int)':
watching.cpp:39:9: warning: unused variable 'wb' [-Wunused-variable]
   39 |     int wb = 0, w2b = 0;
      |         ^~
watching.cpp:39:17: warning: unused variable 'w2b' [-Wunused-variable]
   39 |     int wb = 0, w2b = 0;
      |                 ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 2 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 16032 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 135 ms 15956 KB Output is correct
4 Correct 130 ms 16048 KB Output is correct
5 Correct 126 ms 16056 KB Output is correct
6 Correct 136 ms 15956 KB Output is correct
7 Correct 127 ms 16080 KB Output is correct
8 Correct 126 ms 16044 KB Output is correct
9 Correct 125 ms 16052 KB Output is correct
10 Correct 128 ms 16072 KB Output is correct
11 Correct 126 ms 16044 KB Output is correct
12 Correct 136 ms 15956 KB Output is correct
13 Correct 138 ms 16048 KB Output is correct
14 Correct 131 ms 16048 KB Output is correct
15 Correct 129 ms 16052 KB Output is correct