oj.uz

Submission #878040

# Submission time Handle Problem Language Result Execution time Memory
878040 2023-11-24T03:24:22 Z wii Safety (NOI18_safety) C++17
49 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;

#define int ll
typedef pair<int, int> pii;

#define lx (id << 1)
#define rx (lx | 1)
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const ll Mod2 = ll(1e9) + 9;
const int Lim = 1e6 + 5;
const int inv6 = 166666668;

// #define Sieve
#ifdef Sieve
    vector<int> pr;
    vector<int> lpf;
    void Linear_sieve(int n = Lim) {
        pr.assign(1, 2);
        lpf.assign(n + 1, 2);

        for (int x = 3; x <= n; x += 2) {
            if (lpf[x] == 2) pr.push_back(lpf[x] = x);
            for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
                lpf[pr[i] * x] = pr[i];
        }
    }
#endif

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int base = 3;
const int N = 2e5 + 5;
const int K = log2(N) + 1;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
const int block_size = sqrt(2e9) + 2;

const int N1 = 5e3 + 5;
const int S = 5e3 + 5;

int n, h;
int a[N];
int dp[N1][S];

void subtask7() {
    cerr << "?" << "\n";

    int lim = *max_element(a + 1, a + n + 1);

	foru(i, 1, n) {
        int l = 0, r = 0;
		deque<int> d;

        //cerr << i << ":\n";

		for (int z = 0; z <= lim; ++z) {
            while (!d.empty() && d.front() < z - h) {
				d.pop_front(); ++l;
			}

			while (r <= z + h && r <= lim) {
				while (!d.empty() && dp[i - 1][r] <= dp[i - 1][d.back()])
					d.pop_back();
                d.push_back(r); ++r;
			} 

            //cerr << z << " " << l << " " << r - 1 << "\n";

			dp[i][z] = dp[i - 1][d.front()] + abs(z - a[i]);

            //cout << i << " " << z << " " << dp[i][z] << "\n";
		}
	}

	int ans = Linf;
	for (int z = 0; z <= lim; ++z)
		minimize(ans, dp[n][z]);
	cout << ans;
}

void subtask4() {
    sort(a + 1, a + n + 1);
    int p = a[(n + 1) / 2];

    int ans = 0;
    foru(i, 1, n)
        ans += abs(p - a[i]);
    cout << ans << "\n";
}

int f(int id, int z, int dir) {
    if (id < 1 || id > n) return 0;

    if (dir == 0) {
        int lf = Linf;
        foru(u, z - h, z + h)
            minimize(lf, f(id - 1, u, -1));
        
        int rf = Linf;
        foru(u, z - h, z + h)
            minimize(rf, f(id + 1, u, +1));
        
        return lf + rf + abs(a[id] - z);
    } else {
        int ans = Linf;
        foru(u, z - h, z + h)
            minimize(ans, f(id + dir, u, dir));
        return ans + abs(z - a[id]);
    }
}

void subtask3() {
    int ans = Linf;
    foru(i, 1, n)
        minimize(ans, f(i, a[i], 0));
    cout << ans;
}

void solve() {
    cin >> n >> h;
	foru(i, 1, n) cin >> a[i];

    if (h <= 2 && n <= 10)
        return subtask3();

	if (n < N1 && *max_element(a + 1, a + n + 1) < S) 
		return subtask7();
	
	if (h == 0)
        return subtask4();

    return subtask7();
}

signed main() {
    FastIO;

    #define task "SAFETY"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #define task "test"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #ifdef Sieve
        Linear_sieve();
    #endif

    int ntest = 1;
    // cin >> ntest;
    while (ntest--) {
        //cout << "Case " << q << ": " << "\n"; 
        solve();
        cout << "\n";
    }

    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

safety.cpp:163: warning: "task" redefined
  163 |     #define task "test"
      | 
safety.cpp:157: note: this is the location of the previous definition
  157 |     #define task "SAFETY"
      | 
safety.cpp: In function 'void solve()':
safety.cpp:142:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  142 |     if (h <= 2 && n <= 10)
      |     ^~
safety.cpp:145:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  145 |  if (n < N1 && *max_element(a + 1, a + n + 1) < S)
      |  ^~
safety.cpp: In function 'int main()':
safety.cpp:159:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:160:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:165:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:166:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2396 KB Output is correct
2 Correct 26 ms 2908 KB Output is correct
3 Correct 27 ms 2908 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 3 ms 20828 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 3 ms 20828 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Correct 14 ms 21408 KB Output is correct
21 Correct 14 ms 23132 KB Output is correct
22 Correct 10 ms 19036 KB Output is correct
23 Correct 11 ms 19108 KB Output is correct
24 Correct 14 ms 21084 KB Output is correct
25 Correct 11 ms 19036 KB Output is correct
26 Correct 13 ms 23132 KB Output is correct
27 Correct 13 ms 21084 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 4 ms 22876 KB Output is correct
17 Correct 3 ms 20828 KB Output is correct
18 Correct 3 ms 16732 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Correct 14 ms 21408 KB Output is correct
21 Correct 14 ms 23132 KB Output is correct
22 Correct 10 ms 19036 KB Output is correct
23 Correct 11 ms 19108 KB Output is correct
24 Correct 14 ms 21084 KB Output is correct
25 Correct 11 ms 19036 KB Output is correct
26 Correct 13 ms 23132 KB Output is correct
27 Correct 13 ms 21084 KB Output is correct
28 Correct 151 ms 197464 KB Output is correct
29 Correct 99 ms 168788 KB Output is correct
30 Correct 149 ms 195440 KB Output is correct
31 Correct 52 ms 162384 KB Output is correct
32 Correct 113 ms 164572 KB Output is correct
33 Correct 134 ms 197556 KB Output is correct
34 Correct 158 ms 195340 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 3 ms 22876 KB Output is correct
20 Correct 3 ms 22876 KB Output is correct
21 Correct 3 ms 22876 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 3 ms 20828 KB Output is correct
24 Correct 3 ms 16732 KB Output is correct
25 Correct 4 ms 22876 KB Output is correct
26 Correct 14 ms 21408 KB Output is correct
27 Correct 14 ms 23132 KB Output is correct
28 Correct 10 ms 19036 KB Output is correct
29 Correct 11 ms 19108 KB Output is correct
30 Correct 14 ms 21084 KB Output is correct
31 Correct 11 ms 19036 KB Output is correct
32 Correct 13 ms 23132 KB Output is correct
33 Correct 13 ms 21084 KB Output is correct
34 Correct 151 ms 197464 KB Output is correct
35 Correct 99 ms 168788 KB Output is correct
36 Correct 149 ms 195440 KB Output is correct
37 Correct 52 ms 162384 KB Output is correct
38 Correct 113 ms 164572 KB Output is correct
39 Correct 134 ms 197556 KB Output is correct
40 Correct 158 ms 195340 KB Output is correct
41 Execution timed out 2419 ms 262144 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 21 ms 2396 KB Output is correct
20 Correct 26 ms 2908 KB Output is correct
21 Correct 27 ms 2908 KB Output is correct
22 Correct 3 ms 22876 KB Output is correct
23 Correct 3 ms 22876 KB Output is correct
24 Correct 3 ms 22876 KB Output is correct
25 Correct 4 ms 22876 KB Output is correct
26 Correct 3 ms 20828 KB Output is correct
27 Correct 3 ms 16732 KB Output is correct
28 Correct 4 ms 22876 KB Output is correct
29 Correct 14 ms 21408 KB Output is correct
30 Correct 14 ms 23132 KB Output is correct
31 Correct 10 ms 19036 KB Output is correct
32 Correct 11 ms 19108 KB Output is correct
33 Correct 14 ms 21084 KB Output is correct
34 Correct 11 ms 19036 KB Output is correct
35 Correct 13 ms 23132 KB Output is correct
36 Correct 13 ms 21084 KB Output is correct
37 Correct 151 ms 197464 KB Output is correct
38 Correct 99 ms 168788 KB Output is correct
39 Correct 149 ms 195440 KB Output is correct
40 Correct 52 ms 162384 KB Output is correct
41 Correct 113 ms 164572 KB Output is correct
42 Correct 134 ms 197556 KB Output is correct
43 Correct 158 ms 195340 KB Output is correct
44 Execution timed out 2419 ms 262144 KB Time limit exceeded
45 Halted 0 ms 0 KB -