# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
243140 | 2020-06-30T12:20:27 Z | xiryss | 구경하기 (JOI13_watching) | C++17 | 311 ms | 16248 KB |
//#pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") /*#pragma GCC optimize("section-anchors") #pragma GCC optimize("profile-values,profile-reorder-functions,tracer") #pragma GCC optimize("vpt") #pragma GCC optimize("rename-registers") #pragma GCC optimize("move-loop-invariants") #pragma GCC optimize("unswitch-loops") #pragma GCC optimize("function-sections") #pragma GCC optimize("data-sections") #pragma GCC optimize("branch-target-load-optimize") #pragma GCC optimize("branch-target-load-optimize2") #pragma GCC optimize("btr-bb-exclusive")*/ //#pragma comment(linker, "/STACK:367077216") #define _CRT_SECURE_NO_WARNINGS #include <chrono> #include <set> #include <map> #include <deque> #include <string> #include <cstdint> #include <cmath> #include <queue> #include <cassert> #include <random> #include <bitset> #include <iomanip> #include <numeric> #include <time.h>////////////// #include <ctime> #include <string> #include <cstdio> #include <vector> #include <cstdlib> #include <iostream> #include <algorithm> #include <unordered_map> #include <unordered_set> //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ //#define endl '\n' #define mp make_pair #define pbc push_back #define pob pop_back() #define empb emplace_back #define queuel queue<long long> #define sqr(a) ((a) * (a)) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pin(p) cin >> p.first >> p.second; #define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin()); #define rev(v) reverse(v.begin(), v.end()); #define sout(s, c) for (auto i : s) cout << i << c; #define pout(p) cout << p.first << " " << p.second; #define er(v, l, r) erase(v.begin() + l, v.begin() + r); #define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i]; #define vout(v, c) for (int i = 0; i < v.size(); ++i) cout << v[i] << c; #define pushi(v, a) for (int i = 0; i < a.size(); ++i) v.push_back(a[i]); #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); srand(time(NULL)) #define dab(v) for(auto i:v)cout<<i<<' '; #define sp system("pause") //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ using namespace std; //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ typedef long long ll; typedef long double ld; typedef unsigned long long ull; //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++ mt19937 rnd(time(0) + 228 + 'k' + 'e' + 'k' + 'e' + 'r' + 'o' + 'f' + 'e' + 'y'); const ld EPS = 1e-10; bool checkprime(int x) { for (int i = 2; i * i <= x; ++i) if (x % i == 0) return 0; return 1; } const ld PI = acos(-1); const int MOD7 = 1000000007; const int MOD9 = 1000000009; int mod = MOD7; const int inf = 1e9; int n, p, q; vector<int> a; const int MAXN = 2e3 + 2; int dp[MAXN][MAXN]; bool check(int w) { for (int i = 0; i < MAXN; ++i) fill(dp[i], dp[i] + MAXN, -inf); dp[0][p] = q; for (int i = 0; i < n; ++i) { int clo = lower_bound(all(a), a[i] + w) - a.begin(); int cl = lower_bound(all(a), a[i] + 2 * w) - a.begin(); for (int j = 0; j<=p; ++j) { if (j) { dp[clo][j - 1] = max(dp[clo][j - 1], dp[i][j]); } if (dp[i][j]) { dp[cl][j] = max(dp[cl][j], dp[i][j] - 1); } } } for (int i = 0; i <= p; ++i) { if (dp[n][i] >= 0) return 1; } return 0; } signed main() { cin >> n >> p >> q; p = min(p, n); q = min(q, n); a.resize(n); vin(a); sort(all(a)); int l = 0, r = 1e9; while (r - l > 1) { int m = (l + r) / 2; if (check(m)) r = m; else l = m; } cout << r; // sp; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 75 ms | 16000 KB | Output is correct |
2 | Correct | 70 ms | 16000 KB | Output is correct |
3 | Correct | 73 ms | 16000 KB | Output is correct |
4 | Correct | 70 ms | 16000 KB | Output is correct |
5 | Correct | 70 ms | 16000 KB | Output is correct |
6 | Correct | 73 ms | 16056 KB | Output is correct |
7 | Correct | 75 ms | 16000 KB | Output is correct |
8 | Correct | 70 ms | 16000 KB | Output is correct |
9 | Correct | 72 ms | 16000 KB | Output is correct |
10 | Correct | 74 ms | 16000 KB | Output is correct |
11 | Correct | 78 ms | 16000 KB | Output is correct |
12 | Correct | 75 ms | 16000 KB | Output is correct |
13 | Correct | 77 ms | 16000 KB | Output is correct |
14 | Correct | 72 ms | 16000 KB | Output is correct |
15 | Correct | 72 ms | 16000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 85 ms | 16248 KB | Output is correct |
2 | Correct | 72 ms | 16000 KB | Output is correct |
3 | Correct | 257 ms | 16000 KB | Output is correct |
4 | Correct | 300 ms | 16120 KB | Output is correct |
5 | Correct | 101 ms | 16128 KB | Output is correct |
6 | Correct | 311 ms | 16080 KB | Output is correct |
7 | Correct | 81 ms | 16000 KB | Output is correct |
8 | Correct | 114 ms | 16120 KB | Output is correct |
9 | Correct | 172 ms | 16000 KB | Output is correct |
10 | Correct | 303 ms | 16000 KB | Output is correct |
11 | Correct | 104 ms | 16000 KB | Output is correct |
12 | Correct | 228 ms | 16000 KB | Output is correct |
13 | Correct | 88 ms | 16000 KB | Output is correct |
14 | Correct | 90 ms | 16000 KB | Output is correct |
15 | Correct | 94 ms | 16000 KB | Output is correct |