oj.uz

Submission #210834

# Submission time Handle Problem Language Result Execution time Memory
210834 2020-03-18T19:11:02 Z Nucleist Watching (JOI13_watching) C++14
100 / 100
 932 ms 71524 KB 
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
ll n,p,q,w;
set<ll> hed;
ve hedi;
map<ll,ll>pos;
ll dp[3001][3001];
ll next1[3001][2];
ll solve(ll index,ll rem)
{
    if(index==(hed.size()-1))return 0;
    if(dp[index][rem]!=-1)return dp[index][rem];
    ll ans=pow(10,16);
    if(rem>0)
    {
        ans=min(ans,solve(next1[index][1],rem-1));
    }
    {
        ans=min(ans,1+solve(next1[index][0],rem));
    }
    return dp[index][rem]=ans;
}
int main()
{
  //flash;
  cin>>n>>p>>q;
  memset(dp,-1,sizeof dp);
  for (ll i = 0; i < n; ++i)
  {
    ll xo;
    cin>>xo;
    hed.insert(xo);
  }
  hed.insert(30000000000);
  ll ans=-1;
  for(auto it:hed){hedi.pb(it);pos[it]=hedi.size()-1;}
  ll low=1;
  ll high=INF;
  while(low<=high)
  {
    ll med=(low+high)/2;
    w=med;
    for (int i = 0; i < n; ++i)
    {
       auto u=hed.lower_bound(hedi[i]+w);
       auto k=pos[(*u)];
       next1[i][0]=k;
       u=hed.lower_bound(hedi[i]+2*w);
       k=pos[(*u)];
       next1[i][1]=k;
    }
    memset(dp,-1,sizeof dp);
    ll k = solve(0,min(q,n));
    if(k<=p)
    {
        ans=med;
        high=med-1;
    }
    else
    {
        low=med+1;
    }
  }
  cout<<ans;
  return 0;
}
//code the AC sol !
// BS/queue/map

Compilation message

watching.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
watching.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
watching.cpp: In function 'long long int solve(long long int, long long int)':
watching.cpp:32:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(index==(hed.size()-1))return 0;
        ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 70880 KB Output is correct
2 Correct 374 ms 70928 KB Output is correct
3 Correct 374 ms 70904 KB Output is correct
4 Correct 368 ms 70904 KB Output is correct
5 Correct 375 ms 71004 KB Output is correct
6 Correct 371 ms 71032 KB Output is correct
7 Correct 378 ms 70952 KB Output is correct
8 Correct 368 ms 70988 KB Output is correct
9 Correct 379 ms 70776 KB Output is correct
10 Correct 379 ms 70996 KB Output is correct
11 Correct 387 ms 70880 KB Output is correct
12 Correct 382 ms 70880 KB Output is correct
13 Correct 396 ms 70876 KB Output is correct
14 Correct 370 ms 70904 KB Output is correct
15 Correct 369 ms 70904 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 71160 KB Output is correct
2 Correct 375 ms 70904 KB Output is correct
3 Correct 784 ms 71416 KB Output is correct
4 Correct 443 ms 71524 KB Output is correct
5 Correct 849 ms 71288 KB Output is correct
6 Correct 853 ms 71280 KB Output is correct
7 Correct 387 ms 71160 KB Output is correct
8 Correct 545 ms 71420 KB Output is correct
9 Correct 448 ms 71188 KB Output is correct
10 Correct 476 ms 71408 KB Output is correct
11 Correct 932 ms 71372 KB Output is correct
12 Correct 852 ms 71388 KB Output is correct
13 Correct 413 ms 71160 KB Output is correct
14 Correct 393 ms 71160 KB Output is correct
15 Correct 399 ms 71144 KB Output is correct