Submission #1326433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326433		Valenz	Watching (JOI13_watching)	C++20	100 / 100	841 ms	31920 KiB

watching

// 道草を楽しめ 大いにな。ほしいものより大切なものが きっとそっちに ころがってる
#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;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t; // available on 64-bit targets
 
//defines
#define int long long
#define debug(x) cerr << "(" << #x << "=" << x << "," << __LINE__ << ")\n";
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);
 
//constants
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; 
const char dir[4]{'D','R','U','L'};
const int maxn=2e5+5;
const double eps=1e-9;
 
//typedefs
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
 
//Template
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <typename T, auto M> struct Mod {
    using V = conditional_t<sizeof(T) <= 4, u64, u128>;
    static V inv(V x, V m) { return x > 1 ? m - inv(m % x, x) * m / x : 1; }
    make_unsigned_t<T> x;
    Mod() : x(0) {}
    Mod(auto y) : x(y % M) { x >= M ? x += M : x; }
    operator T() const { return x; }
    Mod operator-() const { return Mod() -= *this; }
    Mod operator+(auto rhs) const { return Mod(*this) += rhs; }
    Mod operator-(auto rhs) const { return Mod(*this) -= rhs; }
    Mod operator*(auto rhs) const { return Mod(*this) *= rhs; }
    Mod operator/(auto rhs) const { return Mod(*this) /= rhs; }
    Mod &operator+=(Mod rhs) { return (x += rhs.x) >= M ? x -= M : x, *this; }
    Mod &operator-=(Mod rhs) { return (x -= rhs.x) >= M ? x += M : x, *this; }
    Mod &operator*=(Mod rhs) { return x = x * V(rhs.x) % M, *this; }
    Mod &operator/=(Mod rhs) { return x = x * inv(rhs.x, M) % M, *this; }
    Mod pow(auto y) const { // O(log y) | 0^(-inf,0] -> 1
    Mod ans(1), base(*this);
    for (auto e = y < 0 ? ~y + u128(1) : +y; e; e >>= 1, base *= base) {
        e & 1 ? ans *= base : ans;
    }
    return y < 0 ? Mod(1) /= ans : ans;
    }
};
 
using mint = Mod<int, 998244353>;

void solve()
{
    int n,p,q;
    cin >> n >> p >> q;
    vector<int> a(n);
    for(int i=0;i<n;i++)
    {
        cin >> a[i];    
    } 
    p=min(p,n);
    q=min(q,n);
    sort(all(a));
    int l=0,r=1e9,ans=1e9;
    while(l<=r)
    {
        int mid=(l+r)/2;
        vector<vector<int>> dp(n+1,vector<int>(p+1,1e12));
        dp[0][0]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=p;j++)
            {
                if(dp[i][j]>q)
                {
                    continue;
                }
                //use small camera
                int next=lower_bound(all(a),a[i]+mid)-a.begin();
                if(j+1<=p)
                {
                    dp[next][j+1]=min(dp[next][j+1],dp[i][j]);
                }
                // use big
                next=lower_bound(all(a),a[i]+2*mid)-a.begin();
                dp[next][j]=min(dp[next][j],dp[i][j]+1);
            }
        }
        bool flag=0;
        for(int i=0;i<=p;i++)
        {
            if(dp[n][i]<=q)
            {
                flag=1;
                break;
            }
        }
        if(flag)
        {
            ans=mid;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    fastio();
    int t=1;
    // cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50