oj.uz

Submission #792927

# Submission time Handle Problem Language Result Execution time Memory
792927 2023-07-25T11:08:41 Z Cookie Watching (JOI13_watching) C++14
50 / 100
 1000 ms 16068 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e9;
const int mxn = 3e5 + 5;
int n, p, q;
int dis[2005][2005], a[2005];
bool ck(int mid){
    forr(i, 1, n + 2){
        forr(j, 0, p + 1){
            dis[i][j] = inf;
        }
    }
    deque<pii>dq;
    dq.pb({1, 0}); dis[1][0] = 0;
    while(!dq.empty()){
        auto [id, small] = dq.front(); dq.pop_front();
        
        if(id == n + 1){
            return(dis[id][small] <= q);
        }
        int nwid = upper_bound(a + 1, a + n + 1, a[id] + mid - 1) - a;
        if(small < p && dis[nwid][small + 1] > dis[id][small]){
            dis[nwid][small + 1] = dis[id][small];
            dq.push_front(make_pair(nwid, small + 1));
        }nwid = upper_bound(a + 1, a + n + 1, a[id] + 2 * mid - 1) - a;
        if(dis[nwid][small] > dis[id][small] + 1){
            dis[nwid][small] = dis[id][small] + 1;
            dq.pb(make_pair(nwid, small));
        }
        
    }
    return(0);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> p >> q; p = min(p, n);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    
    
    int l = 0, r = 5e8, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ck(mid)){
            ans = mid; r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << ans;
    
    return(0);
}

Compilation message

watching.cpp: In function 'bool ck(int)':
watching.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [id, small] = dq.front(); dq.pop_front();
      |              ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 1 ms 712 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 720 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 518 ms 16068 KB Output is correct
4 Correct 54 ms 15956 KB Output is correct
5 Correct 94 ms 8980 KB Output is correct
6 Correct 62 ms 16064 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 100 ms 9356 KB Output is correct
9 Correct 286 ms 14272 KB Output is correct
10 Correct 121 ms 16068 KB Output is correct
11 Correct 117 ms 9072 KB Output is correct
12 Execution timed out 1085 ms 16060 KB Time limit exceeded
13 Halted 0 ms 0 KB -