Submission #878040

#	Time	Username	Problem	Language	Result	Execution time	Memory
878040		wii	Safety (NOI18_safety)	C++17	49 / 100	2419 ms	262144 KiB

safety

#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 (stderr)

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 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29