Submission #443973

#TimeUsernameProblemLanguageResultExecution timeMemory
443973KhizriWatching (JOI13_watching)C++17
100 / 100
817 ms31788 KiB
#include <bits/stdc++.h> using namespace std; //------------------------------DEFINE------------------------------ //****************************************************************** #define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0) #define ll long long #define pb push_back #define F first #define S second #define INF 1e18 #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pii pair<int,int> #define pll pair<ll,ll> #define OK cout<<"Ok"<<endl; #define MOD (ll)(1e9+7) #define endl "\n" //****************************************************************** //----------------------------FUNCTION------------------------------ //****************************************************************** ll gcd(ll a,ll b){ if(a>b) swap(a,b); if(a==0) return a+b; return gcd(b%a,a); } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } bool is_prime(ll n){ ll k=sqrt(n); if(n==2) return true; if(n<2||n%2==0||k*k==n) return false; for(int i=3;i<=k;i+=2){ if(n%i==0){ return false; } } return true; } //***************************************************************** //--------------------------MAIN-CODE------------------------------ const int mxn=2000+5; ll t=1,n,arr[mxn],a,b,color[mxn],dp[mxn][mxn]; vector<ll>vt; ll cal(int ind,ll dis){ ll k=vt[min(ind,(int)vt.size()-1)]+dis-1; ll ans=ind; for(int i=ind;i<vt.size();i++){ if(vt[i]<=k){ ans++; } else{ break; } } return ans; } int check(int x,int y,ll dis){ x=min(n,x*1ll); y=min(n,y*1ll); dp[0][0]=0; for(int i=1;i<=x;i++){ dp[i][0]=cal(dp[i-1][0],dis); } for(int i=1;i<=y;i++){ dp[0][i]=cal(dp[0][i-1],2*dis); } for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++){ dp[i][j]=max(cal(dp[i-1][j],dis),cal(dp[i][j-1],2*dis)); } } if(dp[x][y]==n){ return true; } return false; } void solve(){ cin>>n>>a>>b; for(int i=1;i<=n;i++){ cin>>arr[i]; vt.pb(arr[i]); } sort(all(vt)); ll l=0,r=1e9,k=0; while(l<=r){ ll m=(l+r)/2; if(check(a,b,m)){ r=m-1; k=m; } else{ l=m+1; } } cout<<k<<endl; } int main(){ IOS; //cin>>t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

watching.cpp: In function 'long long int cal(int, long long int)':
watching.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=ind;i<vt.size();i++){
      |                ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...