Submission #270189

#TimeUsernameProblemLanguageResultExecution timeMemory
270189MarcoMeijerBuilding Bridges (CEOI17_building)C++14
30 / 100
317 ms1532 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e18 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } template<class H> void OUTLS(const H& h) {OUTL(h); } template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); } //===================// // Added libraries // //===================// //===================// //end added libraries// //===================// void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 1e6+10; int n; int h[MX], w[MX]; ll dp[MX]; ll SQ(ll x) {return x*x;} void program() { IN(n); RE(i,n) IN(h[i]); RE(i,n) IN(w[i]); ll totW = 0; RE(i,n) totW += w[i]; if(n <= 1000) { dp[0] = -w[0]; REP(i,1,n) { dp[i] = INF; REP(j,0,i) dp[i] = min(dp[i], dp[j] + SQ(h[i]-h[j]) - w[i]); } ll ans = dp[n-1] + totW; OUTL(ans); return; } ll ans = INF; REI(W,-20,20) { set<int> s; REP(i,1,n) { int mid = (h[0]+h[i])/2; ans = min(ans, SQ(h[i]-h[n-1]) + SQ(h[i]-h[0]) - w[i] + totW); auto it = s.lower_bound(mid); if(it != s.end()) { ans = min(ans, SQ(h[0]-*it) + SQ(*it-h[i]) + SQ(h[i]-h[n-1]) - w[i] - W + totW); } it = s.upper_bound(mid); if(it != s.begin()) { it--; ans = min(ans, SQ(h[0]-*it) + SQ(*it-h[i]) + SQ(h[i]-h[n-1]) - w[i] - W + totW); } if(w[i] == W) s.insert(h[i]); } } OUTL(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...