Submission #420291

#TimeUsernameProblemLanguageResultExecution timeMemory
420291_fractalSafety (NOI18_safety)C++14
66 / 100
511 ms1540 KiB
/** * author: fractal * timus: 288481RF **/ #include <bits/stdc++.h> using namespace std; #define F first #define S second #define mp make_pair #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define sz(x) (int)x.size() #define len(x) (int)strlen(x) #define all(x) x.begin(), x.end() #define debug cerr << "OK\n"; #define ub upper_bound #define lb lower_bound #define nl printf("\n"); #define clbuff fflush(stdin); #define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end()) mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef set<int> si; typedef set<ll> sll; typedef set<pii> spii; typedef set<pll> spll; typedef multiset <int> msi; typedef multiset <ll> msll; typedef map <int, int> mi; typedef map <ll, ll> mll; const int N = 1e5 + 2; const int M = 1e5; const int mod = 0; const int inf = 2e9 + 3; const ll INF = 1e11; const ld pi2 = 2.0 * 3.141592; const ld pi = 3.141592; const ld eps = 1e-12; const int dx[4] = {1, -1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; void files(string s = "main") { #ifndef PC freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); #endif } int add(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } int mul(int a, int b) { return a * 1LL * b % mod; } int binpow(int a, int n) { int ret = 1; while (n) { if (n & 1) ret = mul(ret, a); a = mul(a, a); n >>= 1; } return ret; } ll ans = 0, n, h, a[N]; vector<pll> v, u; int main() { speed; cin >> n >> h; if (n > 5000) { cout << -1 << '\n'; return 0; } for (int i = 1; i <= n; ++i) cin >> a[i]; v.pb({-INF, -1}); v.pb({a[1], 1}); ans = 0; for (int i = 2; i <= n; ++i) { for (int j = 0; j < sz(v) - 1; ++j) { u.pb(v[j]); if (v[j].S < 0 && v[j + 1].S > 0) { u.pb({v[j + 1].F, 0}); } } u.pb(v.back()); v = u; u.clear(); for (auto &it : v) it.F += (it.S <= 0 ? -h : h); for (int j = 0; j < sz(v); ++j) { if (v[j].S == 0) { if (a[i] < v[j].F) ans += v[j].F - a[i]; if (a[i] > v[j + 1].F) ans += a[i] - v[j + 1].F; } } for (int j = 0; j < sz(v); ++j) { if (v[j].F < a[i]) { if (sz(u) == 0 || u.back().S != v[j].S - 1) { if (sz(u) && u.back().F == v[j].F) u.ppb(); u.pb({v[j].F, v[j].S - 1}); } if (j + 1 < sz(v) && v[j + 1].F > a[i]) { if (sz(u) && u.back().F == a[i]) u.ppb(); if (sz(u) == 0 || u.back().S != v[j].S + 1) u.pb({a[i], v[j].S + 1}); } else if (j + 1 == sz(v)) { if (sz(u) && u.back().F == a[i]) u.ppb(); if (sz(u) == 0 || u.back().S != v[j].S + 1) u.pb({a[i], v[j].S + 1}); } } else { if (sz(u) && u.back().F == v[j].F) u.ppb(); if (sz(u) == 0 || u.back().S != v[j].S + 1) u.pb({v[j].F, v[j].S + 1}); } } v = u; u.clear(); } cout << ans << '\n'; }

Compilation message (stderr)

safety.cpp: In function 'int mul(int, int)':
safety.cpp:74:21: warning: division by zero [-Wdiv-by-zero]
   74 |  return a * 1LL * b % mod;
      |         ~~~~~~~~~~~~^~~~~
safety.cpp: In function 'void files(std::string)':
safety.cpp:62:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
safety.cpp:63:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...