oj.uz

Submission #1116785

# Submission time Handle Problem Language Result Execution time Memory
1116785 2024-11-22T11:26:46 Z Peter2017 Watching (JOI13_watching) C++14
100 / 100
 152 ms 16208 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 2e3 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

int n;
int P;
int Q;
int a[N];
int f[N][N];

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void input(){
	cin >> n >> P >> Q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
}

bool check(int len){
	if (P + Q >= n) return 1;
	mem(f, 0x3f);
	int idA = 1;
	int idB = 1;
	f[0][0] = 0;
	for (int i = 1; i <= n; i++){
		while (a[i] - a[idA] + 1 > len) idA++;
		while (a[i] - a[idB] + 1 > 2 * len) idB++;
		for (int j = 0; j <= min(i, P); j++){
			mini(f[i][j + 1], f[idA - 1][j]);
			mini(f[i][j], f[idB - 1][j] + 1);
			if (j > 0) mini(f[i][j], f[i][j - 1]);
		}
	}
	return f[n][min(n, P)] <= Q;
}

void solve(){
	sort(a + 1, a + n + 1);
	int l = 1, r = 1e9, ans = r;
	while (l <= r){
		int m = (l + r) >> 1;
		if (check(m)){
			ans = m;
			r = m - 1;
		} else l = m + 1;
	}
	cout << ans;
}

int main(){
    load();
    input();
    solve();
}

Compilation message

watching.cpp: In function 'void load()':
watching.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15952 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 11 ms 16012 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 13 ms 16200 KB Output is correct
8 Correct 13 ms 15952 KB Output is correct
9 Correct 14 ms 15952 KB Output is correct
10 Correct 14 ms 16204 KB Output is correct
11 Correct 13 ms 15952 KB Output is correct
12 Correct 14 ms 15952 KB Output is correct
13 Correct 12 ms 15952 KB Output is correct
14 Correct 11 ms 15952 KB Output is correct
15 Correct 10 ms 15952 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 15 ms 16208 KB Output is correct
8 Correct 31 ms 16208 KB Output is correct
9 Correct 125 ms 16208 KB Output is correct
10 Correct 152 ms 16112 KB Output is correct
11 Correct 26 ms 16208 KB Output is correct
12 Correct 114 ms 16208 KB Output is correct
13 Correct 16 ms 16208 KB Output is correct
14 Correct 14 ms 16208 KB Output is correct
15 Correct 14 ms 16208 KB Output is correct