/*
╓╥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();
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
7764 KB |
Output is correct |
| 2 |
Correct |
249 ms |
8016 KB |
Output is correct |
| 3 |
Incorrect |
246 ms |
7764 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4556 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
247 ms |
7764 KB |
Output is correct |
| 7 |
Correct |
249 ms |
8016 KB |
Output is correct |
| 8 |
Incorrect |
246 ms |
7764 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
