oj.uz

Submission #367451

# Submission time Handle Problem Language Result Execution time Memory
367451 2021-02-17T11:47:15 Z Sparky_09 Watching (JOI13_watching) C++17
100 / 100
 244 ms 38252 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

template <class T>
void rd(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void wr(T x) {
	if (x < 0) putchar('-'), wr(-x);
	else if (x < 10) putchar(x + '0');
	else wr(x / 10), putchar(x % 10 + '0');
}

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
const ll maxn = 6020;
ll p, q, n, dp[maxn][maxn], a[maxn];

bool solve(ll len){
  ll l = 1, r = 1;
  rep(i, 1, n+1){
      while(a[l] < a[i]-len+1) l++;
      while(a[r] < a[i]-2*len+1) r++;
      rep(j,0,p+1){
         dp[i][j] = 1e17;
         if(j) dp[i][j] = dp[l-1][j-1];
         dp[i][j] = min(dp[r-1][j]+1,dp[i][j]);
      }
  }
  return (dp[n][p] <= q ? true : false);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
    cin >> n >> p >> q;
    if(p + q >= n){ cout << 1; return 0; }
    rep(i, 1, n+1) cin >> a[i];
    sort(a+1, a+n+1);
    ll l = 1, h = 1e9+30;
    while(l<=h){
        ll mid = (l+h)/2;
        if(solve(mid)) h=mid-1;
        else l=mid+1;
    }
    cout << l;
}

Compilation message

watching.cpp: In function 'void usaco(std::string)':
watching.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   33 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 10 ms 8684 KB Output is correct
8 Correct 25 ms 10604 KB Output is correct
9 Correct 112 ms 20332 KB Output is correct
10 Correct 244 ms 38252 KB Output is correct
11 Correct 20 ms 9964 KB Output is correct
12 Correct 142 ms 23916 KB Output is correct
13 Correct 9 ms 8684 KB Output is correct
14 Correct 11 ms 8812 KB Output is correct
15 Correct 10 ms 8832 KB Output is correct