Submission #65846

#	Time	Username	Problem	Language	Result	Execution time	Memory
65846		reality	구경하기 (JOI13_watching)	C++17	100 / 100	351 ms	17072 KiB

watching

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2048;
int s[N];
int p1[N];
int p2[N];
int dp[N][N];
int n,a,b;
int f(int K) {
    for (int i = 1;i <= n;++i) {
        p1[i] = p1[i - 1];
        p2[i] = p2[i - 1];
        while (s[i] - s[p1[i] + 1] + 1 > K)
            ++p1[i];
        while (s[i] - s[p2[i] + 1] + 1 > 2 * K)
            ++p2[i];
    }
    for (int i = 0;i <= n;++i)
        for (int j = 0;j <= a;++j)
            dp[i][j] = b + 5;
    dp[0][0] = 0;
    for (int i = 1;i <= n;++i)
        for (int j = 0;j <= a;++j) {
            smin(dp[i][j],dp[p2[i]][j] + 1);
            if (j > 0)
                smin(dp[i][j],dp[p1[i]][j - 1]),
                smin(dp[i][j],dp[i][j - 1]);
        }
    return dp[n][a] <= b;
}
int main(void) {
    cin>>n>>a>>b;
    if (a + b >= n)
        return puts("1") * 0;
    for (int i = 1;i <= n;++i)
        cin>>s[i];
    sort(s + 1,s + 1 + n);
    int ans = 1e9;
    for (int t = 1 << 29;t;t /= 2)
        if (ans > t && f(ans - t))
            ans -= t;
    cout << ans << '\n';
    return 0;
}

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