oj.uz

Submission #707815

# Submission time Handle Problem Language Result Execution time Memory
707815 2023-03-10T08:39:27 Z Alihan_8 Watching (JOI13_watching) C++17
100 / 100
 318 ms 31604 KB 
#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define int long long
const int N = 2e3+1;
int dp[N][N];
bool chmin(int &x, int y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, P, Q; cin >> n >> P >> Q;
    chmin(P, n), chmin(Q, n);
    vector <int> p(n);
    for ( auto &i: p ) cin >> i;
    sort(all(p));
    p.resize(unique(all(p))-p.begin());
    n = (int)p.size();
    const int inf = 1e16+1;
    auto ok = [&](int w){
        for ( int i = 0; i <= n; i++ ){
            for ( int j = 0; j <= P; j++ ){
                dp[i][j] = inf;
            }
        }
        for ( int i = 0; i <= P; i++ ) dp[0][i] = 0;
        auto f = [&](int x){
            return lower_bound(all(p), x)-p.begin();
        };
        for ( int i = 1; i <= n; i++ ){
            int L = f(p[i-1]-w*2+1), R = f(p[i-1]-w+1);
            for ( int j = 0; j <= P; j++ ){
                chmin(dp[i][j], dp[L][j]+1);
                if ( j ) chmin(dp[i][j], dp[R][j-1]);
            }
        }
        return dp[n][P] <= Q;
    };
    int l = 1, r = 1e9;
    while ( l < r ){
        int md = (l+r) >> 1;
        if ( ok(md) ) r = md;
        else l = md+1;
    }
    cout << l;

    cout << '\n';
}

Compilation message

watching.cpp: In function 'void IO(std::string)':
watching.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8424 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 248 ms 31480 KB Output is correct
4 Correct 297 ms 31456 KB Output is correct
5 Correct 19 ms 9588 KB Output is correct
6 Correct 289 ms 31604 KB Output is correct
7 Correct 9 ms 8532 KB Output is correct
8 Correct 26 ms 10288 KB Output is correct
9 Correct 139 ms 19948 KB Output is correct
10 Correct 318 ms 31596 KB Output is correct
11 Correct 22 ms 9684 KB Output is correct
12 Correct 179 ms 23668 KB Output is correct
13 Correct 10 ms 8532 KB Output is correct
14 Correct 11 ms 8668 KB Output is correct
15 Correct 13 ms 8732 KB Output is correct