# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
879310 | 2023-11-27T06:28:27 Z | hasan2006 | 구경하기 (JOI13_watching) | C++17 | 634 ms | 31944 KB |
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 2000 + 9 , mod = 1e9 + 7; ll a[N] = {}, b[N] , c[N] , d[N] , dp[N][N]; void solve() { ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn = 1e18 , mx = 0; cin>>n>>x>>y; for(i = 1; i <= n; i++){ cin>>a[i]; } sort(a + 1 , a + n + 1); l = 1 , r = 1e9; x = min(x , n), y = min(y , n); while(l != r){ m = (l + r) / 2; ll l1 = 1 , r1 = 1; for(i = 1; i <= n; i++){ l1 = max(l1 , i); r1 = max(r1 , i); while(l1 < n && a[l1 + 1] - a[i] + 1 <= m) l1++; while(r1 < n && a[r1 + 1] - a[i] + 1 <= 2 * m) r1++; b[i] = l1; c[i] = r1; } for(i = 0; i <= x; i++) for(j = 0; j <= y; j++) dp[i][j] = 0; for(i = 0; i <= x; i++){ for(j = 0; j <= y; j++){ if(i) dp[i][j] = max(dp[i][j] , dp[i - 1][j]) , dp[i][j] = max(dp[i][j] , b[dp[i - 1][j] + 1]); if(j) dp[i][j] = max(dp[i][j] , dp[i][j - 1]), dp[i][j] = max(dp[i][j] , c[dp[i][j - 1] + 1]); } } if(dp[x][y] == n) r = m; else l = m + 1; } cout<<l<<"\n"; } int main(){ int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 2396 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 2 ms | 2652 KB | Output is correct |
7 | Correct | 0 ms | 348 KB | Output is correct |
8 | Correct | 0 ms | 348 KB | Output is correct |
9 | Correct | 1 ms | 2396 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 1 ms | 2396 KB | Output is correct |
12 | Correct | 1 ms | 2392 KB | Output is correct |
13 | Correct | 0 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 344 KB | Output is correct |
3 | Correct | 358 ms | 25284 KB | Output is correct |
4 | Correct | 28 ms | 31580 KB | Output is correct |
5 | Correct | 24 ms | 2652 KB | Output is correct |
6 | Correct | 634 ms | 31944 KB | Output is correct |
7 | Correct | 2 ms | 2396 KB | Output is correct |
8 | Correct | 15 ms | 2676 KB | Output is correct |
9 | Correct | 16 ms | 12636 KB | Output is correct |
10 | Correct | 29 ms | 31324 KB | Output is correct |
11 | Correct | 26 ms | 2648 KB | Output is correct |
12 | Correct | 144 ms | 17236 KB | Output is correct |
13 | Correct | 1 ms | 2392 KB | Output is correct |
14 | Correct | 1 ms | 2396 KB | Output is correct |
15 | Correct | 1 ms | 2396 KB | Output is correct |