oj.uz

Submission #342764

# Submission time Handle Problem Language Result Execution time Memory
342764 2021-01-02T17:53:58 Z mohamedsobhi777 Watching (JOI13_watching) C++14
100 / 100
 413 ms 16236 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 2000 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

__int128 read()
{
       __int128 x = 0, f = 1;
       char ch = getchar();
       while (ch < '0' || ch > '9')
       {
              if (ch == '-')
                     f = -1;
              ch = getchar();
       }
       while (ch >= '0' && ch <= '9')
       {
              x = x * 10 + ch - '0';
              ch = getchar();
       }
       return x * f;
}
void print(__int128 x)
{
       if (x < 0)
       {
              putchar('-');
              x = -x;
       }
       if (x > 9)
              print(x / 10);
       putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }

int n, p, q;
int dp[N][N];

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);

       cin >> n >> p >> q;

       vi a(n);
       for (auto &u : a)
              cin >> u;
       sort(all(a));
       q = min(q, n);
       p = min(p, max(0, n - q));
       vi go(n + 1, 0), go2(n + 1, 0);

       auto check = [&](int mid) -> bool {
              int j1 = 0, j2 = 0;
              inc(i, 0, n - 1)
              {
                     while (j1 + 1 < n && a[j1 + 1] <= a[i] + mid - 1)
                            ++j1;
                     while (j2 + 1 < n && a[j2 + 1] <= a[i] + mid * 2 - 1)
                            ++j2;
                     go[i] = j1 - i + 1;
                     go2[i] = j2 - i + 1;
              }
              inc(i, 0, n)
                  memset(dp[i], 0, sizeof dp[i]);
              inc(i, 0, p)
              {
                     inc(j, 0, q)
                     {
                            if (i + 1 <= p)
                                   dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + go[dp[i][j]]);
                            if (j + 1 <= q)
                                   dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + go2[dp[i][j]]);
                     }
              }
              inc(i, 0, p) inc(j, 0, q) if (dp[i][j] >= n) return 1;
              return 0;
       };

       int ans = 1e9, lo = 1, hi = 1e9;

       while (lo <= hi)
       {
              int mid = (lo + hi) >> 1;
              if (check(mid))
                     ans = mid, hi = mid - 1;
              else
                     lo = mid + 1;
       }

       cout << ans;
       return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1132 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 2 ms 1132 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 3 ms 1132 KB Output is correct
13 Correct 2 ms 1132 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16108 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 335 ms 16140 KB Output is correct
4 Correct 120 ms 16108 KB Output is correct
5 Correct 71 ms 16108 KB Output is correct
6 Correct 69 ms 16236 KB Output is correct
7 Correct 72 ms 16108 KB Output is correct
8 Correct 101 ms 16108 KB Output is correct
9 Correct 110 ms 16108 KB Output is correct
10 Correct 138 ms 16108 KB Output is correct
11 Correct 131 ms 16160 KB Output is correct
12 Correct 413 ms 16160 KB Output is correct
13 Correct 72 ms 16236 KB Output is correct
14 Correct 71 ms 16108 KB Output is correct
15 Correct 74 ms 16108 KB Output is correct