제출 #577339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577339		Mounir	구경하기 (JOI13_watching)	C++14	100 / 100	382 ms	31760 KiB

watching

#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 / 50
• Subtask 2: 50 / 50