제출 #1281759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281759		baotoan655	구경하기 (JOI13_watching)	C++20	100 / 100	103 ms	16332 KiB

watching

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 2005;
int n, P, Q;
int a[N];
int dp[N][N], pr[N][2];
bool chk(int len) {
    for(int i = 1, j = 1; i <= n; ++i) {
        while(j < i && a[i] - a[j] + 1 > len) ++j;
        pr[i][0] = j;
    }
    for(int i = 1, j = 1; i <= n; ++i) {
        while(j < i && a[i] - a[j] + 1 > 2 * len) ++j;
        pr[i][1] = j;
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= i; ++j) {
            dp[i][j] = min(dp[i][j], dp[pr[i][0] - 1][j] + 1);
            if(j > 0) dp[i][j] = min(dp[i][j], dp[pr[i][1] - 1][j - 1]);
        }
    }
    int mn = 1e9;
    for(int i = 0; i <= Q; ++i) mn = min(mn, dp[n][i]);
    return mn <= P;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    file("A") else file("task");
    cin >> n >> P >> Q;
    P = min(P, n);
    Q = min(Q, n);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = 1e9, mid, res;
    while(l <= r) {
        mid = l + r >> 1;
        if(chk(mid)) r = (res = mid) - 1;
        else l = mid + 1;
    }
    cout << res << '\n';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp: In function 'int main()':
watching.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:5: note: in expansion of macro 'file'
   35 |     file("A") else file("task");
      |     ^~~~
watching.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:5: note: in expansion of macro 'file'
   35 |     file("A") else file("task");
      |     ^~~~
watching.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:20: note: in expansion of macro 'file'
   35 |     file("A") else file("task");
      |                    ^~~~
watching.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:35:20: note: in expansion of macro 'file'
   35 |     file("A") else file("task");
      |                    ^~~~

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