Submission #1106442

#TimeUsernameProblemLanguageResultExecution timeMemory
1106442tradzBuilding Bridges (CEOI17_building)C++14
30 / 100
111 ms131072 KiB
#include <bits/stdc++.h> #define int long long #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define For(i,a,b) for(int i = a; i <= b; i++) #define Ford(i,a,b) for(int i = a; i >= b; i--) #define ll long long #define ii pair<int,int> #define fi first #define se second #define all(v) v.begin(),v.end() #define RRH(v) v.resize(unique(all(v)) - v.begin()) using namespace std; const int N = 1e6+7; const int M = 1e9+7; const ll oo = 3e18; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); long long GetRandom(long long l, long long r) { return uniform_int_distribution<long long> (l, r)(rng); } int n, w[N], h[N]; namespace sub1 { int dp[N], pre[N]; void solve() { pre[0] = 0; For (i, 1, n) pre[i] = pre[i - 1] + w[i]; dp[1] = 0; For (i, 2, n) { dp[i] = oo; for (int j = i - 1; j >= 1; j--) { dp[i] = min(dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + pre[i - 1] - pre[j], dp[i]); } //cout << i << " " << dp[i] << '\n'; } cout << dp[n] << '\n'; } } namespace subac { int dp[N], pre[N]; struct Line { ll a, b; Line() {} Line(ll a_, ll b_) { a = a_, b = b_; } ll operator()(ll x) const { return a*x+b; } }; struct seg { ll l, r, mid; Line val = Line(0, 1e16); seg() {} seg(ll l_, ll r_) { l = l_, r = r_, mid = (l + r) / 2; } seg *lc = NULL, *rc = NULL; void newNode() { if (l + 1 == r || lc != NULL) return; lc = new seg(l, mid); rc = new seg(mid, r); } void add(Line k) { if (k(mid) < val(mid)) swap(k, val); if (l + 1 == r) return; newNode(); if (k.a > val.a) lc->add(k); else rc->add(k); } ll get(ll x) { if (l + 1 == r || lc == NULL) return val(x); if (x < mid) return min(val(x), lc->get(x)); else return min(val(x), rc->get(x)); } } T; void solve() { pre[0] = 0; For (i, 1, n) pre[i] = pre[i - 1] + w[i]; For (i, 1, n) dp[i] = oo; dp[1] = 0; Line bruh; bruh.a = -2ll * h[1]; bruh.b = 1ll * h[1] * h[1] - pre[1]; T.add(bruh); For (i, 2, n) { dp[i] = pre[i - 1] + 1ll * h[i] * h[i] + T.get(h[i]); bruh.b = dp[i] - pre[i] + 1ll * h[i] * h[i]; bruh.a = -2ll * h[i]; T.add(bruh); } cout << dp[n] << '\n'; } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); #define TASK "" if (fopen (".inp", "r")) { freopen (".inp", "r", stdin); freopen (".out", "w", stdout); } if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } cin >> n; For (i, 1, n) cin >> h[i]; For (i, 1, n) cin >> w[i]; if (n <= 1000) { sub1 :: solve(); return 0; } subac :: solve(); cerr << "Time elapsed: " << TIME << " s.\n"; return 0; }

Compilation message (stderr)

building.cpp: In function 'int32_t main()':
building.cpp:102:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen (".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:103:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen (".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...