oj.uz

답안 #577338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577338 2022-06-14T14:49:21 Z Mounir 구경하기 (JOI13_watching) C++14
50 / 100
 12 ms 16412 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 = 1e3 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 724 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 696 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 696 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 692 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 16412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -