Submission #986433

#TimeUsernameProblemLanguageResultExecution timeMemory
986433Zero_OPWatching (JOI13_watching)C++14
100 / 100
63 ms16472 KiB
#include<bits/stdc++.h> using namespace std; using int64 = int64_t; #define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i) #define FORD(i, r, l) for(int i = (r), _l = (l); i >= _l; --i) #define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i) #define repd(i, r, l) for(int i = (r) - 1, _l = l; i >= _l; --i) #define left __left #define right __right #define next __next #define prev __prev #define div __div #define pb push_back #define pf push_front #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define compact(v) v.erase(unique(all(v)), end(v)) #define dbg(v) "[" #v " = " << (v) << "]" #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } template<typename T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } template<int dimension, typename T> struct vec : public vector<vec<dimension - 1, T>> { static_assert(dimension > 0, "Dimension must be positive !\n"); template<typename... Args> vec(int n = 0, Args... args) : vector<vec<dimension - 1, T>> (n, vec<dimension - 1, T>(args...)) {} }; template<typename T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) {} }; void preprocess(); void init(); void process(); int main(){ ios_base::sync_with_stdio(0); cin.tie(0); file("antuvu"); preprocess(); int T = 1; //cin >> T; while(T--){ init(); process(); } return 0; } const int MAX = 2e3 + 5; int n, p, q, a[MAX], reach_w[MAX], reach_2w[MAX], dp[MAX][MAX]; void preprocess(){ } void init(){ cin >> n >> p >> q; for(int i = 1; i <= n; ++i){ cin >> a[i]; } } bool f(int w){ for(int i = 1, j = 1, k = 1; i <= n; ++i){ while(j < n && a[j + 1] - a[i] + 1 <= w){ ++j; } reach_w[i] = j; while(k < n && a[k + 1] - a[i] + 1 <= 2 * w){ ++k; } reach_2w[i] = k; } if(reach_w[1] == n || reach_2w[1] == n) return true; memset(dp, -1, sizeof(dp)); dp[0][1] = reach_2w[1]; dp[1][0] = reach_w[1]; for(int i = 0; i <= p; ++i){ for(int j = 0; j <= q; ++j) if(i || j){ if(dp[i][j] == n){ return true; } dp[i + 1][j] = max(dp[i + 1][j], reach_w[dp[i][j] + 1]); dp[i][j + 1] = max(dp[i][j + 1], reach_2w[dp[i][j] + 1]); } } return false; } void process(){ if(p + q >= n){ cout << 1 << '\n'; return; } sort(a + 1, a + 1 + n); int l = 1, r = 1e9, ans = r; while(l <= r){ int mid = l + r >> 1; if(f(mid)) ans = mid, r = mid - 1; else l = mid + 1; } cout << ans << '\n'; }

Compilation message (stderr)

watching.cpp: In function 'void process()':
watching.cpp:127:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |         int mid = l + r >> 1;
      |                   ~~^~~
watching.cpp: In function 'int main()':
watching.cpp:21:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 | #define    file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:55:5: note: in expansion of macro 'file'
   55 |     file("antuvu");
      |     ^~~~
watching.cpp:21:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 | #define    file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:55:5: note: in expansion of macro 'file'
   55 |     file("antuvu");
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...