oj.uz

Submission #577339

# Submission time Handle Problem Language Result Execution time Memory
577339 2022-06-14T14:49:52 Z Mounir Watching (JOI13_watching) C++14
100 / 100
 382 ms 31760 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
#define int long long
using namespace std;

const int N = 2e3 + 5, OO = 1e14;

int nVals, nbs[2], sizes[2];
vector<int> vals;
int apres[N][2], dp[N][N];

bool possible(int w){
      sizes[0] = w;
      sizes[1] = 2 * w;

      vector<int> pts(2, 0);
      for (int i = 0; i < 2; ++i)
            for (int deb = 0; deb < nVals; ++deb){
                  chmax(pts[i], deb);
                  while (pts[i] < nVals && vals[pts[i]] - vals[deb] < sizes[i])
                        ++pts[i];
                  apres[deb][i] = pts[i];
            }
      
      if (false){
            cout << "---" << endl;
            for (int i = 0; i < nVals; ++i)
                  cout << apres[i][0] << " " << apres[i][1] << endl;
      }

      for (int i = 0; i <= nVals; ++i)
            for (int j = 0; j <= nbs[0]; ++j)
                  dp[i][j] = OO;
      dp[nVals][0] = 0;
      for (int deb = nVals - 1; deb >= 0; --deb){
            for (int nPris = 0; nPris <= nbs[0]; ++nPris){
                  if (nPris != 0) chmin(dp[deb][nPris], dp[apres[deb][0]][nPris - 1]);
                  chmin(dp[deb][nPris], dp[apres[deb][1]][nPris] + 1);
            }
      }

      bool ok = false;
      for (int nPris = 0; nPris <= nbs[0]; ++nPris){
            ok |= (dp[0][nPris] <= nbs[1]);
            if (false)
                  cout << nPris << ": " << dp[0][nPris] << endl;
      }
      return ok;
}

signed main(){ 
      cin >> nVals >> nbs[0] >> nbs[1];
      chmin(nbs[0], nVals);
      vals.resize(nVals);
      for (int& val : vals)
            cin >> val;
      sort(all(vals));
      int deb = 1, fin = 1e9;
      while (fin > deb){
            int mid = (deb + fin)/2;
            if (possible(mid))
                  fin = mid;
            else
                  deb = mid + 1;
      }
      cout << deb << endl;
      return 0;   
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 804 KB Output is correct
5 Correct 1 ms 724 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 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 283 ms 31756 KB Output is correct
4 Correct 362 ms 31700 KB Output is correct
5 Correct 20 ms 9556 KB Output is correct
6 Correct 382 ms 31760 KB Output is correct
7 Correct 9 ms 8660 KB Output is correct
8 Correct 27 ms 10324 KB Output is correct
9 Correct 140 ms 20180 KB Output is correct
10 Correct 344 ms 31760 KB Output is correct
11 Correct 24 ms 9684 KB Output is correct
12 Correct 191 ms 23764 KB Output is correct
13 Correct 8 ms 8532 KB Output is correct
14 Correct 9 ms 8660 KB Output is correct
15 Correct 8 ms 8644 KB Output is correct