oj.uz

Submission #65846

# Submission time Handle Problem Language Result Execution time Memory
65846 2018-08-09T02:18:50 Z reality Watching (JOI13_watching) C++17
100 / 100
 351 ms 17072 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 1160 KB Output is correct
8 Correct 3 ms 1160 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 3 ms 1160 KB Output is correct
11 Correct 3 ms 1160 KB Output is correct
12 Correct 4 ms 1160 KB Output is correct
13 Correct 3 ms 1160 KB Output is correct
14 Correct 3 ms 1160 KB Output is correct
15 Correct 3 ms 1284 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8856 KB Output is correct
2 Correct 2 ms 8856 KB Output is correct
3 Correct 2 ms 8856 KB Output is correct
4 Correct 2 ms 8856 KB Output is correct
5 Correct 2 ms 8856 KB Output is correct
6 Correct 2 ms 8856 KB Output is correct
7 Correct 15 ms 8992 KB Output is correct
8 Correct 35 ms 9140 KB Output is correct
9 Correct 168 ms 16968 KB Output is correct
10 Correct 351 ms 17072 KB Output is correct
11 Correct 24 ms 17072 KB Output is correct
12 Correct 176 ms 17072 KB Output is correct
13 Correct 14 ms 17072 KB Output is correct
14 Correct 15 ms 17072 KB Output is correct
15 Correct 15 ms 17072 KB Output is correct