Submission #1272344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272344		abyfu	Watching (JOI13_watching)	C++20	0 / 100	128 ms	580 KiB

watching

//OwO
//#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define namein "input.txt"
#define nameout "output.txt"
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
#define m_pi acos(-1)
using namespace std;
const ll inf = 7e18;    
const int linf = 1e8;

void file(){
    if (fopen(namein, "r")){
        freopen(namein, "r", stdin);
        freopen(nameout, "w", stdout);
    }   
}

const ll mod = 998244353;
const int N = 2e3 + 5, M = 5e5 + 5;
int w;
int n, p, q;
pair<int, int> dp[N];
int a[N];

void run(){
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        //cout << a[i] << " ";
    }
    //cout << "\n";
    sort(a + 1, a + 1 + n);
    int l = 1, r = a[n] - a[1];
    //cout << a[1] << " " << a[n] << "\n";
    while (l <= r){
        int mid = (l + r)/2;
        w = mid;
        dp[0].fi = dp[0].se = 0;
        for (int i = 1; i <= n; i++) dp[i].fi = dp[i].se = linf/2;
        for (int i = 1; i <= n; i++){
            for (int j = i; j >= 1; j--){
                int u = dp[j - 1].fi, v = dp[j - 1].se;
                if (u != linf/2){
                    if (a[i] - a[j] + 1 <= 2*w){
                        if (a[i] - a[j] + 1 > w){
                            if (v + 1 <= q){
                                if (u + v + 1 < dp[i].fi + dp[i].se){
                                    dp[i].fi = u; dp[i].se = v + 1;
                                }
                                else if (u + v + 1 == dp[i].fi + dp[i].se){
                                    if (min(u, v + 1) < min(dp[i].fi, dp[i].se)){
                                        dp[i].fi = u; dp[i].se = v + 1;
                                    }
                                    else if (min(u, v + 1) == min(dp[i].fi, dp[i].se)){
                                        if (max(u, v + 1) <= max(dp[i].fi, dp[i].se)){
                                            dp[i].fi = u; dp[i].se = v + 1;
                                        }
                                    }
                                }
                            }
                        }
                        else {
                            if (v + 1 <= q){
                                if (u + v + 1 < dp[i].fi + dp[i].se){
                                    dp[i].fi = u; dp[i].se = v + 1;
                                }
                                else if (u + v + 1 == dp[i].fi + dp[i].se){
                                    if (min(u, v + 1) < min(dp[i].fi, dp[i].se)){
                                        dp[i].fi = u; dp[i].se = v + 1;
                                    }
                                    else if (min(u, v + 1) == min(dp[i].fi, dp[i].se)){
                                        if (max(u, v + 1) <= max(dp[i].fi, dp[i].se)){
                                            dp[i].fi = u; dp[i].se = v + 1;
                                        }
                                    }
                                }
                            }
                            if (u + 1 <= p){
                                if (u + v + 1 < dp[i].fi + dp[i].se){
                                    dp[i].fi = u + 1; dp[i].se = v;
                                }
                                else if (u + v + 1 == dp[i].fi + dp[i].se){
                                    if (min(u, v + 1) < min(dp[i].fi, dp[i].se)){
                                        dp[i].fi = u + 1; dp[i].se = v;
                                    }
                                    else if (min(u, v + 1) == min(dp[i].fi, dp[i].se)){
                                        if (max(u, v + 1) <= max(dp[i].fi, dp[i].se)){
                                            dp[i].fi = u + 1; dp[i].se = v;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if (dp[n].fi != linf/2){
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << l;
}   

int main(){
   run();
}

Compilation message (stderr)

watching.cpp: In function 'void file()':
watching.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(namein, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
watching.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(nameout, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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