제출 #878036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878036		wii	Safety (NOI18_safety)	C++17	35 / 100	146 ms	197460 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 = Inf;
	for (int z = 0; z <= lim; ++z)
		minimize(ans, dp[n][z]);
	cout << ans;
}

void subtask2() {

}

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

	if (n < N1 && *max_element(a + 1, a + n + 1) < S) 
		return subtask7();
	
	return subtask2();
}

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
**/

컴파일 시 표준 에러 (stderr) 메시지

safety.cpp:123: warning: "task" redefined
  123 |     #define task "test"
      | 
safety.cpp:117: note: this is the location of the previous definition
  117 |     #define task "SAFETY"
      | 
safety.cpp: In function 'int main()':
safety.cpp:119:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:120:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:125:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:126:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29