제출 #881802

#제출 시각아이디문제언어결과실행 시간메모리
881802HA_Blue2809Building Bridges (CEOI17_building)C++14
100 / 100
52 ms73348 KiB
// G&B  7&&      #&&&#     J&&&&&&&J     G&&&&  &&&  B&5 B&P  J&#  &&&&&& #&&&&&&&5 //
// B@#  ?@@     #@&#@&     Y@@57Y@@J    B@@     @@7  #@P #@G  Y@@  @@     J@@57J@@P //
// B@#7#&@@    &@& 5@&     J@@   @@J   B@@  B#  @@7  #@P #@G  Y@@  @@###Y 7@@   &@P //
// B@#  5@@   &@&  P@&     Y@@   @@J  #@@    @  @@?  &@P #@G  5@@  @@     ?@@   &@P //
// B@#  7@@  @@@@B P@&     Y@@   @@J #@@@&&@@@  @@@&&@@G #@@&&@@@  @@&#&& 7@@   &@G //
//      7@#        P@P           &@?                          P@G               &@? //
//      ?#         PP            &7                           5G                &7  //
//      7          7             7                            7                 7   //
#include <bits/stdc++.h>
#define file "XAYCAU"
#define FastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
#define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
#define endl " \n"
#define _ <<' '<<
#define el <<'\n'
#define f first
#define s second
#define mp make_pair
#define mp3(a,b,c) mp(a,mp(b,c))
#define pb push_back
#define eb emplace_back
#define si(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mset(a,i) memset(a,i,sizeof a)
#define maxi(a,b) a=max(a,b)
#define mini(a,b) a=min(a,b)
#define bit(x,i) (((x)&P[i])>0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<ll,ll> pii;
typedef pair<int,pii> piii;
typedef pair<pii,pii> p4;
const int maxn=1e6+69;
const ll mod=1e9+7;
struct line{
 ll a,b;
 ll operator()(ll x){
  return a*x+b;
 }
}T[maxn*4];
int n;
ll H[maxn],W[maxn],F[maxn],sum=0;
void add(line a,int it=1,int l=0,int r=1e6){
 if (r-l==1){
  if (a(l)<T[it](l)) T[it]=a;
  return;
 }
 int mid=(l+r)>>1,t=it<<1,p=it<<1|1;
 if (T[it].a<a.a) swap(T[it],a);
 if (T[it](mid)>a(mid)){
  swap(T[it],a);
  add(a,t,l,mid);
 }
 else add(a,p,mid,r);
}
ll get(int x,int it=1,int l=0,int r=1e6){
 if (r-l==1) return T[it](x);
 int mid=(l+r)>>1,t=it<<1,p=it<<1|1;
 if (x<mid) return min(T[it](x),get(x,t,l,mid));
 return min(T[it](x),get(x,p,mid,r));
}
int main()
{
 FastIO; OpenFile;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>H[i];
 for(int i=1;i<=n;i++){
  cin>>W[i];
  sum+=W[i];
 }
 for(int i=0;i<maxn*4;i++)
  T[i]={(ll)1e9,(ll)1e18};
 F[1]=-W[1];
 for(int i=2;i<=n;i++){
  add({-2LL*H[i-1],H[i-1]*H[i-1]+F[i-1]});
  F[i]=get(H[i])+H[i]*H[i]-W[i];
 }
 cout<<F[n]+sum;
 return 0;
}

//                                                                         ▒███████▓▒░
//                                                                      ███▓░░░░░░░████▓
//                                                                    ░██░░░░░░░░███▓ ░▒
//                                ██████████████████████████          ██░░░░░░░██▓▓█████▒
//                          ███████░░░░░░░███░░░░░░░░░░░░░░░███▓    ▓███░░░░░████▒░░░▒████
//              █████████████░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░████████▓▓██░░░███░░░░░░░░░░██░
//              ▒██░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░░░░░░░░▓██████▓▓▓▓██░██▓░░░░░░░░░░░░▒█
//               ░███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▓▓▓▓██▓███████▓████████░░░░░░█▓
//                  ███▓░░░░░░██░░░░░░░█░░░░░░░░░░░░░█▓░░░░░▒█▓▓▓▓▓▓██▓▓███▓▓▓█▓    ███░░░██▒
//                    █▓░░░░██░░░░░░░░█▓░░░░░░░░░░░░░░█▓░░░░░░███▓▓▓██▓▓▓▓▓▓▓██      ░█▓░███
//                  ▒█▒░░░██░░░░░░░░░██░░░░░░░░░░░░░░▓██▓░░░░░░▒█████████▓▓▓███      ▓████░
//                 ░█▒░░░██░░░░░░░░░░██░░░░░░░░░░░░░░████░░░░░░░░░░▒█████████░▓█     ███
//                 ██░░░██░░░░░░░░░░▒█▒░░░░░░░░░░░░░██░▓██░░░░░░░░░░░░░░░░█▓░░░█▓
//                ▒█▒░░░█▒░░░░░░░░░░▒█▒░░░░░░░░░░░░▓██░░▒██░░░░░░░░░░░░░░░░░░░░▒█░
//                ██░░░███░░░░░░░░░░██▒░░░░░░░░░░░▒██░░░░░██░░░░░░░░░░░░░░░░░░░░██
//               ██░░░▒███░░░░░░░░████▓░░░░░░█░░░▒██▒░░░░░░██░░░░░░░░█▒▒██░░░░░░██▓
//              ██░░░░████░░░░░░██▓  ██░░░░░██░░▒██░█▒░░░░░░██░░░░░░░██▒▒██░░░░░░██░
//             ██░░░░██░▒██░░░░█▓    ▒█▒░░░███░▓█▒  ▓█░░░░░░▒█▒░░░░░░▒██░░██░░░░░░██░
//           ░█▒░░░░██░░░███▒▒█▒      ▓█░░░█████░    ▓██░░░░░██░░░░░░░██░░░██░░░░░░████▒    ▓
//          ██░░░░░██▒░░▓█░████        ▓█▓▒█░█▓       ░██▓░░░░██░░░░░░▓█▓░░▒██▓░░░░░░░▓██████
//        ░█▒░░░░░██▓░░██               ░███ ░          ▒███░░██░░░░░░▒██░░░████▓░░░░░░▒██▓
//       ███████████░▒█▒  ██                               ▒████▒░░░░░▒██░░░░██▒▓██████▓
//               ██░██░                                        ██░░░░░███░░░░▒██░░██
//              ▒█▓▒█░                                         ▓█░░░░▒██▓░░░░░██▓░░█▒
//              ██░█▓                                     ██   ▓▓░░░▒███▒░░░░░▒██░░█▓
//              ██░▒█              ██████████████              █▒░░█████░░░░░░░██░░█▒
//              ██░░██             █▓▓▓▓▓▓▓▓▓▓▓██             ░█░▓██▓██▓░░░░░░░██░░█▒
//              ██░████░            ██▓▓▓▓▓▓▓▓██              █████ ░██░░░░░░░███░░█░
//              ██████▓██             █▓▓▓▓▓▓██              ▓█▓░  ▒█▓░░░░░░░░██░░░█░
//               ███ ██░░██░            █████                    ░██░░░░░░░░░██▒░░░█░
//                   ██░░░░███░                              ░░██▓░░░░░░░░░░██▒░░░░█░
//                    ██░░▓░░░███▓░                       ▒███▓░░░░░░░░░░░███░░░░░░█▒
//                     ██████▓░░░▒████▓░                   ░█▓░░░░░░░░░░██▓ ██▓░░░░▒█
//                      ▓██ ░████████████████▓▓░░░░░░░░░░▒██████▓▒▒▒▓██▓     ▒███▒░░██
//                        ▒ ▒█████░ ▓█▓▓▓▓███▓████████████░░░▒█████░░▒█▒         ▒████
//                       ▒▓████▓    ▒█▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓█       ▓███████
//                       ▓███▓▓▓▓   ░█▓▓▓▓███▓▓▓▓▓▓▓▓▓▓██      ▓▓▓▓▓████▓
//                    ░████░███▓▓▓█▓  ░████▓██▓██████████▓▒  ░▓▓▓▓████▓██▓
//                  ░███    ░█████   ██▓▓██▓▓▒███▓███▒   ███░▓▓▓▓███░▒████▒
//               ▒██▒░██   ██████     ███   ▓▓  ░█████    ░████████░ ░██░▓▓█▒                    ░██
//███████████████▒░░░░▒█░  ██░░░█░          ▒▓            ▓█░░░▒█░   ██░░▒▓████▓▓░               ████
// █▒░░░░░░░██▒░░░░░░░▒█░  ▒█▒░████▓▓▓▓█████████▒       ▓████▓██░   ██▓░░▓▓░░▒▓▓███░           ███░▒██
// ░██░░▒██▓░░░░░░░░░░▓██  ░██░   ░ ▒█▓▓▓▓▓▓▓▓▓▓██████████░   █▓   ██▒░░░▒▓░▒▓▓░░█████████████▓░░░░░██
//    ██▓░░░░░░░░░░▒██▓ █▓ ░█░   ███████████▓▓▓▓▓███████████████▒██████░░░▓▓▓▓░░░░░░░░███▒░░░░░░░░░██
//   ▓█░░░░░░░░▓██▒     ░█▓███████▓▓▓▓██████████████▓▓▓▓▓▓▓▓▓▓████▓    ▓██▓▓▓░░░░░░░░░░░░░▓██▒░░░███
//   █▒░░░░░░▓██          ████▓▓▓▓▓████ ██▓▓▓▓▓▓▓█░████▓▓▓▓▓▓▓████▒      ▓▓▓▓███▒░░░░░░░░░░░▒█████▒
//   █▓░░░░░██          ░███▓▓▓████▓   ██▓▓▓▓▓▓▓▓█▒  ░█████████▒ ██     ▓▓   ░▓  ███▒░░░░░░░░░███
//   ██▒░░░██           █▓▓██████    ░██▓▓▓▓▓▓▓▓▓█▒    ░███████████    ░▓▓▓▓▓▓▓▒    ▒██▒░░░░░░░██
//    ███░░█▓           ██▓█████████████████████████████▒ █████████                    ██░░░░░░██
//      ▓█████          ████████▒                         ░████████                      █▒░░░░██
//                      ░███████                           ███████▒                       █▒░░▓█
//                       ██████░                            ██████                        ██░▓█▒
//                        ▒███                                ███                         ████░
//                                                                                      ░████

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

building.cpp: In function 'int main()':
building.cpp:12:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
   66 |  FastIO; OpenFile;
      |          ^~~~~~~~
building.cpp:12:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
   66 |  FastIO; OpenFile;
      |          ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...