Submission #482543

#	Time	Username	Problem	Language	Result	Execution time	Memory
482543		silverfox	Watching (JOI13_watching)	C++14	50 / 100	482 ms	1316 KiB

watching

/*
UWOZH SQ ATGZVJNZS

XYW LTBMKST XDPCWVYDYD UWATVZYPE VGK (VUNV) MJ S NPYIIST WVA KZIE REJ WVLXXVV QY 1998
OS TGUMVX KZM ECIWL WQ ZPVUBCJRZU UPYMR KCNC EJ KWQOARJM, RVQVK, XSJXFYZLKLP, NQOZSJ,
GZ XPWZU WGZV KZM TIXVJVPO.

MW QWF OVZWL EJ GFHG ECMJ, QWF HEP TM TNWLWL YJXZXQNVXZGV FIHVJ BSZ
TIGDTNMFFA ZA WVUBTJR 512© FX BSZ HZYQEVP DATWZREACX XSGQZTBLK SKE (YQTS)
BZ ZJWWKE MIDGDLG SW LPP VFFNM-CZTFJBPY MEXZTIKVEMYOW.
*/

#include <algorithm>
#include <utility>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <climits>
#include <cctype>
#include <string>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <random>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>
#include <limits>
using namespace std;

#pragma GCC optimize("O3")
#define TASK ""
#define lnBr cout << '\n'

namespace sub1
{
    int n,p,q;
    const int maxn = 100;
    bool f[maxn+1][maxn+1][maxn+1];
    int a[maxn+1];

    bool check(int w)
    {
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= p; j++)
            {
                for (int k = 0; k <= q; k++) {f[i][j][k] = true;}
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= p; j++)
            {
                for (int k = 0; k <= q; k++)
                {
                    f[i][j][k] = false;

                    if (j > 0)
                    {
                        int mini = max(1, a[i] - w+1);
                        auto it = lower_bound(a+1, a+n+1, mini); int idx = it - a; idx--;
                        f[i][j][k] = f[idx][j-1][k];
                    }

                    if (k > 0)
                    {
                        int mini = max(1, a[i] - 2*w+1);
                        auto it = lower_bound(a+1, a+n+1, mini); int idx = it - a; idx--;
                        f[i][j][k] = f[i][j][k] || f[idx][j][k-1];
                    }

                    //cerr << i << " " << j << " " << k << " " << f[i][j][k] << '\n';
                }
            }
        }
        return f[n][p][q];
    }

    void Solve(int xx)
    {
        n = xx; cin >> p >> q; p = min(p, n); q = min(q, n);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        sort(a+1, a+n+1);
        //cout << check(1) << '\n';

        int low = 1, high = 1e9;
        while(low <= high)
        {
            int w = (low+high)/2;
            if (!check(w)) {low = w+1;} else {high = w-1;}
        }
        cout << low;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }

    int n; cin >> n;
    if (n <= 100)
    {
        sub1::Solve(n);
    }
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50