Submission #1287376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287376		dex111222333444555	구경하기 (JOI13_watching)	C++20	0 / 100	25 ms	16160 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005, infINT = 1e9 + 37237;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
int numVal, numBig, numSmall, val[MAXN], dp[MAXN][MAXN];

void input(){
    cin >> numVal >> numBig >> numSmall;
    numBig = min(numBig, numVal);
    numSmall = min(numSmall, numVal);
    for(int i = 1; i <= numVal; i++) cin >> val[i];
}

bool check(int mid){
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    int j1 = 1, j2 = 1;
    for(int i = 1; i <= numVal; i++){
        while(val[j1] <= val[i] - mid + 1) j1++;
        while(val[j2] <= val[i] - 2 * mid + 1) j2++;
        for(int j = 0; j <= min(numBig, i); j++){
            int dist = val[i] - val[j1] + 1;
            int delta = (dist + mid - 1) / mid;
            if (j1 - 1 == 0) delta = 1;
            minimize(dp[i][j], dp[j1 - 1][j] + delta);
//            if (j == 0 && i == 13) cout << delta << ' ' << dp[i][j] << '\n';
            if (j - 1 >= 0) minimize(dp[i][j], dp[j2 - 1][j - 1]);
        }
//        cout << i << ' ' << j1 << ' ' << j2 << '\n';
    }
    for(int i = 1; i <= numVal; i++)
//    for(int j = 0; j <= numVal; j++) if (dp[i][j] < infINT) cout << i << ' ' << j << ": " << dp[i][j] << '\n';
    for(int j = 0; j <= numBig; j++) if (dp[numVal][j] <= numSmall) return 1;
    return 0;
}

void solve(){
    sort(val + 1, val + 1 + numVal);
    int l = 0, r = 1e9, m, res = -1;
    while(l <= r){
        m = (l + r) >> 1;
        if (check(m)) res = m, r = m - 1;
        else l = m + 1;
    }
    cout << res << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    input();
    solve();
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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