제출 #881820

#제출 시각아이디문제언어결과실행 시간메모리
881820HA_Blue2809Building Bridges (CEOI17_building)C++14
30 / 100
249 ms8016 KiB
/* ╓╥g@&▓▓▓▓▓▓æ▄, ▄@▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╢▓@▄ ▄▓╢▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╢▓▄ ╓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓╢@ ╓▓▒▒▒▓▓▓▓▓╢▓▀"` ``"▀▀▓▓▓▓▓▓▓▓▓▒▒░N ▓╢▓▒▓▓▓▓╢▀` ⌐═" ╙"*¬, `▀▓╢▓▓▓▒▒▓╣▄ ╓▓▓▓▓▓▓▓▓" ⌐` ▄ ▓µ "═, ▀▓▓▓▓▓▓▓▓ ▄╢▓▓▓▓╢▀ ¿" N ▐▒N Æ▒▓ ,╗▌ 'v ╙▓▓▓▓▓▓▓µ ▓▓▓▓▓▓▀ ¿" ╗ Æ▒▒W▒╢╢╢▒╜▒▓╣╨▒▐ ,╣µ ╙, ▀╢▓▓▓▓▓▄ ▓▓▓▓▓▓`," ▐▒╣N▒▒ ╙╣[ ╙" ╙ ╢▒@▒▒▓ , N ╙▓▓▓▓▓╢w ▓▓▓▓▓▀ ▄ ▐▒W▌▒Ñ `╒ ╢▒ [ ▒ ▒▐╓╣▐ ▐ ▓▓▓▓▓▓ ╓▓▓▓▓▓▀ Æ╜╙w█▒ƒ`▒ j ▌ ▌╢⌐ ▐ t I, ╙╢╨▒▒ Æ╜╟ ▓▓▓▓▓█▓▄ ▄▓▓▌▓▓▓▌ ▄▒ ▌░▌ ▐ ▐ M ▌▓▓¿░░░j░j ░M ▓▒╝ ▓ ▓▓▓▓▓╣▓▓▄ ▄╢▓▓▓▓▓▓█ ]▌ ░▒▌ ▓░░▓ W░▌╢╢▓░ ░▐░░░░▌▓ ▐▒▌ ]▌ ╚▓▓▓▓█▓▓▓▓▄ ▄╣▓▓▓▓█▓▓▓ ▓ ▒▒▌ ▀░▓▐░▌░▓▒▒▒▒,,Åw√▌Æ«Ñ▓ j▒▌ ▓ ▀▓▓▓█▓▓▓▓▓▓▄ ╓▓▓▓▓▓▓▓█▓▓▓ j▓ ░▒▓ƒ ╙ `╙w▐▒M ▐▌ ▓▓▓█▓▓▓▓▓▓╢▓ ▄╣▓▓▓▓▓▓▓█▓▓▌ ▐▌ ▌▓▄▄▄▄▄▄~ ;▄▄▄▄▄▄▄▐, j▓ █▓▓█▓▓▓▓▓▓▓▓▓ ▓╢▓▓▓▓▓▓▓▓█▓▓C ▐C █w j█████▌ ▀█▓█▌█▌ █▌ █ ▓▓▓█▓▓▓▓▓▓▓▓▓▓⌐ ▓▓▌▀▓▓▓▓▓▓▓▓▓▓U ▌░M ▐▀╦ █▓╨╢▓▌ ▓▀╜╨▓` ▄▓ █ ▓▓▓█▓▓▓▓▀▓▓╣▓▓▓ ▀▀▀▀▒▒▀▓▀▀▀▀▓▓▌@░░ τ▐ ░░░ⁿ ' '""░░░'j▌,C y└⌐ ▓▓▓ ,▐▓y"▓æ Ñ▒╢▓╖ ▐▓▀╝▓░ ] &▓░░░░ ░░░ ▀g░ jP▄¥▌▓▌ ▒▓@ Æ▀ ╣▒╢▓Æ▀▓▓ ▐░░ ]▓ ▓▀ .≈⌐=. ▓╜ ▒ ,▐ ▐▓▓▄▄▓▓P▀` ╙▒▒╫▓▓▓▌▐░▓░ ▒▓µ ▀ ╢╜╙╙╙╙▌ ▄▌,▓░ ╛▌ ▓▓▌╔╫▀' ╙▒▒µ▓▀,▌▌1░░▐░▓▓ ▀▄▄ "═░²` ▄▄▓▀╓▓░Æ ▐j ▐▓▓φ▒ ╝ ⌐══∞▓ ╙░░▌▓▓▓▄└▓╢▓▄▄, ,▄▄▓▓▓▓▀▄▓░▌▒ ╒▓▓⌐^ ╚▒ ╒ ' ^ⁿ^^╩, W░▌▓▓▀▓▓▓▓▓▓▓░░▒▒▒░░▓▓▓▓▓▄▀▓▓▓░░,╛▌^` ` * Γ ⌐ ^═, "Ñ▌▌ ▓▓ ▀▓▓▒▐░░ ╚░▓ ▐▓▓▌¿╜▀▌▒z`r ^ ] ⌐▐ »@▄▌▄ ╙'▀ⁿ══▀▌⌐⌐Å⌐∞═╩▌─^^▀" ,▒` ƒ ^ y╩╗ ╓4╨` ▐▒N ▀N▄ ╥▄ ║ ,,░@▀░"▓▌ⁿ ░ `ⁿ ,╜ ╖ ▐Ç╣▓⌐ ╙º≡w▄⌂╓;░░░░▐▄▄▄▄▌▄w⌐⌐╤M░╜' ╬╫░ ░▒╙ ,Γ,∞`▓░ ▐▓δ, `▒░░▓ⁿ░░▒▒▒░`Æ'` ╣╬▓ ░▐▐k,¥ ▄Å* ▓░ ▓▓$▄░░░,, $, ,▀⌐ ,░░▓▓▄▓ ░ä/▐ "╧N ┤║░░░░▌╢▓▓▓▓▓█▓▓▄g, ╙▄▒▒▄▀ ,,░░░▄▄▓▓▓▓▓▌,,Ö` L "¬ ▌ ¢░▒░▓▓▌▓▓▓▓▓▓▓▓▓▒╢▓▄, ▐▓▓, ,░▄▓▓▌▒▓▓▓▓▓▓▓╢▌É^ ║ ⌐ ▓░░▐╣▌▓▓▓▓▓▓▓▓▌▒▓▓▓▓▓▄▓▌▄▓▓▓▓▓▓▓▒▐▓▓▓▓▓▓▓/ ▐ ▐ ╜@░▒▌▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓██▓▓▓▓▓▓▒▒▓▓▓▓▓▓^ ╠ ╓╣░ ╝▓▓▓▓▓▓▓▓▓▓▒▐▓▓▓▓▓▓▓▓▓╢▓▓▓▓▓▓▌▒▓▓▓▌▓░ ▒▓▌ ▓▓╣, ░░░░▓█▓▓▓▓▓▓▒▐▓▓▓╢▓▓▓▓▓▓▓▓▓▓▓▓▌▒▓▓▌▓▒░░░ ,║▓▓▌ ▓▓▓▓▓▒░░▒▒▒▒░░▓▀▓▓▓▌▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▐▓▓▒▒▒░░░░╓╫▓▓▓▓ ▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▒█▓▓░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓▒▒▒▒▒░▒╢▓▓▓▓▓▓ ]▓▓▓▓▓▓▓▓▓▓▓@▒▒▒▒▒▐▓▓░▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▓▓▒▒▒▒▒▒▓▓▓▓▓▓▓▓ ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓ ]▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▒▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌█▒▒▒▒▒▒▓▓▓▓▓▓▓▓▓▓▓▄ ▐▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒╣╣▒▒╫▓▓▓▓▓▓▓▓▓▓▓▓▄ ▐▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▐▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓█▀▀╣▒╢▓▓▓▓▓▓▓▓▓▓▓▓▓▓ ▐▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌▒▒▓▓▓▓▓▓▓▓▓▓▓▓▓▓█▀'╔▄▄▄▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌ ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▒▒▓▓▓▓▓▓▓▓▓▓▓█▀ ▓▓▓▓▓█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ ▓▓▓▓▓▓▓▓▓▓▓▓▓█▓▓▓▓▓▓▓▓▒▒▐▓▓▓▓▓▓╣▓▀`▄, ▌▓▓▓▓▓█▓▓▓▓▓▓▓▓▓▓▓▓▓▓▌ */ #include<bits/stdc++.h> // basic typedef long long ll; #define int long long #define oo 1e15 #define MAX 1110001 // support #define pb push_back #define mp make_pair #define p push #define sz(x) ll (x.size()) #define le(s) ll (s.length()) #define YES cout << "YES" << '\n' #define NO cout << "NO" << '\n' // for loops #define forw(i,l,r) for(int i=l; i<=r; i++) #define forb(i,r,l) for(long i=r; i>=l; i--) // pair #define pr pair<ll,ll> #define prr pair<ll,pr> #define rpr pair<pr,ll> #define fi first #define se second // file #define fo "xaycau" #define fr freopen(fo".INP","r",stdin) #define fw freopen(fo".OUT","w",stdout) #define fl {fr; fw;} // one time support #define mulsolv(n) { forw(i,1,n) solve() ;} #define fastIO ios::sync_with_stdio(false), cin.tie(NULL) // debug #define debug(x) cout << #x << " = " << x << '\n' #define debugm(x,n) { forw(i,1,n) cout << ' ' ; debug(x); } #define debugv(v) { cout << " SIZE: " << sz(v) << '\n'; forw(i,0,sz(v)-1) cout << i << " = " << v[i] << '\n'; cout << '\n';} #define debugp(a) { cout << #a << " = " << a.fi << " , " << a.se << '\n'; } #define debugvp(v) { cout << " SIZE: " << sz(v) << '\n'; forw(i,0,sz(v)-1) cout << i << " = " << v[i].fi << " , " << v[i].se << '\n'; cout << '\n';} int mod = 1e9 + 7; using namespace std; int n ; int h[MAX] ; int w[MAX] ; int f[MAX] ; // ---------------------------- SUBTASK 1 ---------------------- int getv(int l , int r ) { if(l > r) return 0 ; return w[r] - w[l-1] ; } int sqr(int n) { return n*n ; } void sub1() { f[1] = 0 ; forw(i,2,n) { f[i] =oo ; forw(j,1,i-1) f[i] = min(f[i] , f[j] + getv(j + 1 , i-1) + sqr( h[i] - h[j])) ; } cout << f[n] << '\n'; } // ---------------------- SIEU TA DAO -------------- int k ; int tadao1() { f[1] = 0 ; forw(i,2,n) { f[i] =oo ; forw(j,1,min(i-1,k)) f[i] = min(f[i] , f[j] + getv(j + 1 , i-1) + sqr( h[i] - h[j])) ; forb(j,i-1,max(1ll, i-k)) f[i] = min(f[i] , f[j] + getv(j + 1 , i-1) + sqr( h[i] - h[j])) ; } return f[n] ; } int tadao3() { int ans = getv(2,n-1) + sqr(h[1] - h[n]) ; forw(i,2,n-1) { int tmp = sqr(h[i] - h[1]) + sqr(h[i] - h[n]) + getv(2,n-1) - getv(i,i); ans = min(ans, tmp) ; } return ans ; } // -------------------- LOBBY ---------------------- void solve(){ cin >> n ; k = 1e8/ n ; forw(i,1,n) cin >> h[i] ; forw(i,1,n) cin >> w[i] ; forw(i,1,n) w[i] = w[i-1] + w[i] ; if(n <= 10000) sub1(); else { int t1 = tadao1(), t3 = tadao3() ; cout << min(t1,t3) ; } } signed main(){ fastIO; if(fopen(fo".INP","r")) fl ; solve(); }

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'int main()':
building.cpp:83:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 | #define fr freopen(fo".INP","r",stdin)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:85:13: note: in expansion of macro 'fr'
   85 | #define fl {fr; fw;}
      |             ^~
building.cpp:180:29: note: in expansion of macro 'fl'
  180 |     if(fopen(fo".INP","r")) fl ;
      |                             ^~
building.cpp:84:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 | #define fw freopen(fo".OUT","w",stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.cpp:85:17: note: in expansion of macro 'fw'
   85 | #define fl {fr; fw;}
      |                 ^~
building.cpp:180:29: note: in expansion of macro 'fl'
  180 |     if(fopen(fo".INP","r")) fl ;
      |                             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...