Submission #1368730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368730		po_rag526	구경하기 (JOI13_watching)	C++17	0 / 100	4 ms	580 KiB

watching

#include<bits/stdc++.h>
using namespace std;

void FREOPEN(const string &prob) {
    freopen((prob + ".in").c_str(), "r", stdin);
    freopen((prob + ".out").c_str(), "w", stdout);
}

#define debug(c) cout << #c << " = " << c << endl
#define debugc() cout << "PASS" << endl

#define nl "\n"
#define fl flush
#define int long long

#define ll long long
#define str string
#define ld long double

#define Pb push_back
#define pB pop_back
#define ub upper_bound
#define lb lower_bound
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define ft first
#define sc second

const ll mod = 1e9+7;
const ld pi = 3.1415926535;

void solve() {
    int n,p,q; cin >> n >> p >> q;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];

    if(p + q >= n) {cout << "0\n"; return;}
    sort(all(a));

    auto f = [&](const int &w) -> bool {
        vector<vector<int>> dp(n+2, vector<int>(p+1, q+5));
        vector<int> nxt1(n+1), nxt2(n+1);
        // dp[i][j] -> berapa banyak kamera besar terkecil yang dibutuin kalau udah di event i terus kamera kecil j

        for(int j=0;j<=p;j++) dp[1][j] = 0;
        for(int i=1;i<=n;i++) {
            auto nxt = ub(all(a), a[i] + w - 1) - a.begin();
            nxt1[i] = nxt;

            auto nxtt = ub(all(a), a[i] + 2*w - 1) - a.begin();
            nxt2[i] = nxtt;
        }

        for(int i=1;i<=n;i++) {
            for(int j=0;j<=p;j++) {
                if(j < p) dp[nxt1[i]][j+1] = min(dp[nxt1[i]][j+1], dp[i][j]);
                dp[nxt2[i]][j] = min(dp[nxt2[i]][j], dp[i][j] + 1);
            }
        }

        for(int j=0;j<=p;j++)
            if(dp[n+1][j] <= q) return 1;
        return 0;
    };

    int l = 1, r = 1e9, ans = r;
    while(l<=r) {
        int m = l + (r-l)/2;

        if(f(m)) ans = m, r = m-1;
        else l = m+1;
    }
    cout << ans << nl;
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0); 
    // FREOPEN("");
    
    int T = 1; //cin >> T;
    while(T--) solve();
}

Compilation message (stderr)

watching.cpp: In function 'void FREOPEN(const std::string&)':
watching.cpp:5:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |     freopen((prob + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:6:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |     freopen((prob + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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