제출 #1207519

#제출 시각아이디문제언어결과실행 시간메모리
1207519liza구경하기 (JOI13_watching)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, p, q; cin >> n >> p >> q; vector<int> v(n); for(int i =0; i < n; i++) cin >> v[i]; sort(v.begin(), v.end()); //for(int i =0; i < n; i++) cout << v[i]; int l = 1, r = 1e9; int rez=1e9; while(l<r) { int m = l+(r-l)/2; int dp[p+1][q+1]={0}; if(p > 0) dp[1][0]=v[0]+m-1; if(q > 0) dp[0][1]=v[0]+2*m-1; int c =0; for(int j = 2; j <= q; j++) { auto y = upper_bound(v.begin(), v.end(), dp[0][j-1]); if(*y>=v[v.size()-1]) { rez=min(rez, m); r=m; c=1; break; } dp[0][j]=*y+2*m-1; } if(c)continue; for(int i = 2; i <= p; i++) { auto x = upper_bound(v.begin(), v.end(), dp[i-1][0]); if(*x>=v[v.size()-1]) { rez=min(rez, m); r=m; c=1; break; } dp[i][0]=*x+m-1; } if(c)continue; for(int i = 1; i <= p; i++) { for(int j = 1; j <= q; j++) { auto x = upper_bound(v.begin(), v.end(), dp[i-1][j]); auto y = upper_bound(v.begin(), v.end(), dp[i][j-1]); if(*x>=v[v.size()-1]|| *y>=v[v.size()-1]) { rez=min(rez, m); r=m; c=1; break; } dp[i][j]=max(*x+m-1, *y+2*m-1); } if(c)break; } if(c)continue; if(dp[p][q]>= v[v.size()-1]) { rez=min(rez, m); r=m; } else { l=m+1; } } rez=min(l, rez); cout << rez << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...