제출 #881820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881820		HA_Blue2809	Building Bridges (CEOI17_building)	C++14	30 / 100	249 ms	8016 KiB

building

/*


                                     ╓╥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 ;
      |                             ^~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40