제출 #269798

#제출 시각아이디문제언어결과실행 시간메모리
269798MarcoMeijerBuilding Bridges (CEOI17_building)C++14
30 / 100
367 ms11676 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 smw[MX]; ll dph[MX]; void program() { IN(n); RE(i,n) IN(h[i]); RE(i,n) IN(w[i]); smw[0]=0; RE(i,n) smw[i+1] = smw[i]+w[i]; RE(i,MX) dph[i] = INF; dp[n-1] = 0; dph[h[n-1]] = smw[n-1]; REV(i,0,n-1) { dp[i] = INF; REP(dif,-1000,1001) { ll j = h[i]+dif; if(j < 0) continue; if(j >= MX) continue; dp[i] = min(dp[i], dph[j] - smw[i+1] + (ll)dif*(ll)dif); } dph[h[i]] = min(dph[h[i]], dp[i]+smw[i]); } OUTL(dp[0]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...