Submission #1084029

#TimeUsernameProblemLanguageResultExecution timeMemory
1084029MrPavlitoWatching (JOI13_watching)C++17
100 / 100
277 ms16220 KiB
#include <bits/stdc++.h> //#define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second #define endl "\n" #define pii pair<int,int> using namespace std; const int MAXN = 2e3+5; const int mod7 = 1e9+7; const long long inf = 1e18; int n,p,q; vector<int> niz; int dp[MAXN][MAXN]; bool solve(int mid) { memset(dp, -1, sizeof(dp)); for(int i=0; i<=p; i++) { for(int j=0; j<=q; j++) { if(i==0 && j == 0)continue; else if(i==0) { int index = dp[i][j-1]+1; int tr = niz[index] + mid+mid-1; int poz = upper_bound(all(niz), tr) - niz.begin()-1; dp[i][j] = poz; } else if(j == 0) { int index = dp[i-1][j]+1; int tr = niz[index] +mid-1; int poz = upper_bound(all(niz), tr) - niz.begin()-1; dp[i][j] = poz; } else { int index1 = dp[i][j-1]+1; int tr = niz[index1] + mid+mid-1; int poz = upper_bound(all(niz), tr) - niz.begin()-1; int index2 = dp[i-1][j]+1; int tr2 = niz[index2] + mid-1; int poz2 = upper_bound(all(niz), tr2) - niz.begin()-1; dp[i][j] = max(poz, poz2); } //cout << dp[i][j] << " "; if(dp[i][j]>=n-1)return 1; } //cout << endl; } return 0; } signed main() { ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0); int tt=1; //cin >> tt; while(tt--) { cin >> n >> p >> q; niz.resize(n); p = min(p,n); q = min(q,n); for(int i=0; i<n; i++)cin >> niz[i]; sort(all(niz)); int l = 1; int r = 1e9+1; int rez = r; if(p+q>= n) { cout << 1 << endl; return 0; } while(l<=r) { int mid = l+r>>1; if(solve(mid)) { rez = mid; r = mid-1; } else l = mid+1; } cout << rez << endl; } }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:84:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |             int mid = l+r>>1;
      |                       ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...