oj.uz

Submission #995501

# Submission time Handle Problem Language Result Execution time Memory
995501 2024-06-09T07:37:53 Z Lilinta Watching (JOI13_watching) C++14
50 / 100
 109 ms 262144 KB 
//Problem link:
// Libraries
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //find_by_order, order_of_key
#include <ext/rope>
using namespace __gnu_cxx;

// Data types
typedef string str;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// Methods
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define sz(a) (int)(a).size()

// Iterator
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

// Variable names
#define y1 y1___

// Loops
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define RFOR(i,a,b) for (int i = (a); i >= (b); --i)

// Constant variables
const int MOD = 1000000007; // 998244353
const int INF = 2000000005;
const ll LLINF = 1000000000000000005LL;
const ld PI = acos((ld)-1);
const ld EPS = 1e-9;

void setIO(str name="") {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(15) << fixed;
    if (fopen((name + ".INP").c_str(), "r")) {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
}

int test = 1;
const int MAXN = 2005;
int n, p, q;
ll arr[MAXN];
//vector<vector<vector<int>>> dp;
vector<vector<vector<int>>> mark;
ll w;
int c = 0;

bool dfs(int i, int p, int q) {
    if (p < 0 || q < 0) return false;
    if (i > n) return true;
    if (mark[i][p][q] == c) return false;
//    dp[i][p][q] = 0;
    mark[i][p][q] = c;
    int j = distance(arr, upper_bound(arr+i+1, arr+n+2, arr[i] + w - 1));
    if (dfs(j, p-1, q)) {
        return true;
    }
    j = distance(arr, upper_bound(arr+i+1, arr+n+2, arr[i] + 2*w - 1));
    if (dfs(j, p, q-1)) {
        return true;
    }
    return false;
}

void solve() {
    cin >> n >> p >> q;
    FOR(i, 1, n) {
        cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    arr[n+1] = LLINF;
    if (p + q >= n) {
        cout << 1 << '\n';
        return;
    }
//    dp = vector(n+1, vector(p+1, vector(q+1, 0)));
    mark = vector<vector<vector<int>>>(n+1, vector<vector<int>>(p+1, vector<int>(q+1, 0)));
    ll l = 0;
    ll r = 1000000001;
    while (l < r) {
        w = l + (r-l)/2;
        ++c;
        if (dfs(1, p, q)) {
            r = w;
        } else {
            l = w + 1;
        }
    }
    cout << l << '\n';
}

int main() {
    setIO();
    //cin >> test;
    while (test--) {
        solve();
    }
    return 0;
}

Compilation message

watching.cpp: In function 'void setIO(str)':
watching.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Runtime error 109 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -