Submission #558021

#TimeUsernameProblemLanguageResultExecution timeMemory
558021Tien_NoobBuilding Bridges (CEOI17_building)C++17
0 / 100
118 ms4660 KiB
//Make CSP great again //You're as beautiful as the day I lost you #include <bits/stdc++.h> #define TASK "TESTCODE" using namespace std; const int N = 2e5; long long dp[N + 1], h[N + 1], w[N + 1], s = 0; int n; long long A(int i) { return -2 * h[i]; } long long B(int j) { return dp[j] + h[j] * h[j]; } long long C(int i) { return h[i] * h[i] - w[i]; } struct CHT { bool Empty = true; vector<long double> Point; vector<int> Line; void Clear() { Point.clear(); Line.clear(); Empty = true; } long double Intersect(int i, int j) { return (long double)(B(j) - B(i))/(A(i) - A(j)); } bool ok(int i) { return Intersect(i, Line.back()) > Intersect(i, Line[Line.size() - 2]); } void Add(int i) { Empty = false; while (Line.size() > 1 || (Line.size() == 1 && A(i) == A(Line.back()))) { if (A(i) == A(Line.back())) { if (B(i) < B(Line.back())) { Line.pop_back(); Point.pop_back(); } else { break ; } } else if (!ok(i)) { Line.pop_back(); Point.pop_back(); } else { break; } } if (Line.empty()) { Point.push_back(-1e18); } else { Point.push_back(Intersect(i, Line.back())); } Line.push_back(i); } long long Get(int i) { int j = upper_bound(Point.begin(), Point.end(), (long double)(h[i])) - Point.begin() - 1; return A(Line[j]) * h[i] + B(Line[j]) + C(i); } }; CHT f[17]; void read() { cin >> n; for (int i = 1; i <= n; ++ i) { cin >> h[i]; } for (int i = 1; i <= n; ++ i) { cin >> w[i]; s += w[i]; } } void Update(int i) { int pos = 0; vector<int> tmp = {i}; while (pos < 17 && !f[pos].Empty) { for (int j : f[pos].Line) { tmp.push_back(j); } f[pos].Clear(); ++pos; } sort(tmp.begin(), tmp.end(), [](int x, int y) { return A(x) > A(y); }); for (int j : tmp) { f[pos].Add(j); } } void solve() { dp[1] = -w[1]; for (int i = 2; i <= n; ++ i) { dp[i] = 1e9; Update(i - 1); for (int j = 0; j < 17; ++ j) { if (!f[j].Empty) { dp[i] = min(dp[i], f[j].Get(i)); } } } cout << dp[n] + s; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); //freopen(TASK".OUT", "w", stdout); } int t = 1; bool typetest = false; if (typetest) { cin >> t; } for (int __ = 1; __ <= t; ++ __) { //cout << "Case " << __ << ": "; read(); solve(); } }

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...