Submission #503125

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
503125	2022-01-07 10:09:58	colossal_pepe	Watching (JOI13_watching)	C++17	100 / 100	153 ms	15200 KiB

watching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define calcdp for (int i = n - 1; i >= 0; i--) { int useq = lower_bound(a, a + n, a[i] + (2 * w)) - a; int usep = lower_bound(a, a + n, a[i] + w) - a; dp[i][0] = dp[useq][0] + 1; for (int j = 1; j <= p; j++) { dp[i][j] = min(dp[useq][j] + 1, dp[usep][j - 1]); } }
 
int n, p, q, a[2005];
int solve() {
    int dp[n + 1][p + 1];
    for (int i = 0; i <= p; i++) {
        dp[n][i] = 0;
    }
    int minw = 1, maxw = 1e9;
    while (maxw - minw >= 2) {
        int w = (maxw + minw) / 2;
        /*
        for (int i = n - 1; i >= 0; i--) {
            int useq = lower_bound(a, a + n, a[i] + (2 * w)) - a;
            int usep = lower_bound(a, a + n, a[i] + w) - a;
            dp[i][0] = dp[useq][0] + 1;
            for (int j = 1; j <= p; j++) {
                dp[i][j] = min(dp[useq][j] + 1, dp[usep][j - 1]);
            }
        }
        */
       calcdp;
       if (dp[0][p] <= q) maxw = w;
       else minw = w + 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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