oj.uz

답안 #367451

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367451 2021-02-17T11:47:15 Z Sparky_09 구경하기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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