제출 #1368737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368737		vjudge1	구경하기 (JOI13_watching)	C++17	100 / 100	205 ms	30364 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 << "1\n"; return;}

    sort(all(a));

    vector<vector<int>> dp(n+3, vector<int>(p+1, 1e18));
    auto f = [&](const int &w) -> bool {
        vector<int> nxt1(n+2), nxt2(n+2);
        for(int i=1;i<=n;i++) {
            auto nxt = lb(all(a), a[i] + w) - a.begin();
            nxt1[i] = nxt;

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

        for(int i=1;i<=n+1;i++)
            for(int j=0;j<=p;j++) dp[i][j] = 1e18;

        dp[1][0] = 0;
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=p;j++) {
                if(j+1 <= 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)/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();
}

컴파일 시 표준 에러 (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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 50 / 50
• 서브태스크 2: 50 / 50