oj.uz

Submission #522040

# Submission time Handle Problem Language Result Execution time Memory
522040 2022-02-03T16:13:00 Z cig32 Watching (JOI13_watching) C++17
100 / 100
 424 ms 31704 KB 
#pragma GCC optimize("Ofast")
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
void solve(int tc) {
  int n, p, q;cin >> n >> p >> q;
  int a[n+1];
  for(int i=1; i<=n; i++)cin >> a[i];
  sort(a+1, a+n+1);
  int lb = 1, rb = 1e9;
  p = min(p, n);
  q = min(q, n);
  while(lb<rb) {
    int w = (lb+rb) >> 1;
    int dp[p+1][q+1];
    for(int i=0;i<=p;i++){
      for(int j=0;j<=q;j++) {
        dp[i][j] = 0;
      }
    }
    int smol[n+1], big[n+1];
    for(int i=1; i<=n; i++) {
      smol[i] = big[i] = i;
      for(int j=i; j<=n; j++) {
        if(a[j] - a[i] + 1 <= w) smol[i] = j;
        if(a[j] - a[i] + 1 <= 2*w) big[i] = j;
      }
    }
    for(int i=0; i<=p; i++) {
      for(int j=0; j<=q; j++) {
        if(i==0 && j==0) continue;
        if((i && dp[i-1][j] == n) || (j && dp[i][j-1] == n)) {
          dp[i][j] = n;
          continue;
        }
        dp[i][j] = 0;
        if(i) dp[i][j] = max(dp[i][j], smol[dp[i-1][j] + 1]);
        if(j) dp[i][j] = max(dp[i][j], big[dp[i][j-1] + 1]);
      }
    }
    if(dp[p][q] == n) rb = w;
    else lb = w + 1;
  }
  cout << lb << "\n";
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 288 ms 17884 KB Output is correct
4 Correct 75 ms 1584 KB Output is correct
5 Correct 76 ms 1580 KB Output is correct
6 Correct 424 ms 31704 KB Output is correct
7 Correct 61 ms 356 KB Output is correct
8 Correct 74 ms 1100 KB Output is correct
9 Correct 91 ms 1096 KB Output is correct
10 Correct 107 ms 1612 KB Output is correct
11 Correct 80 ms 1684 KB Output is correct
12 Correct 165 ms 7888 KB Output is correct
13 Correct 58 ms 364 KB Output is correct
14 Correct 64 ms 364 KB Output is correct
15 Correct 84 ms 360 KB Output is correct