oj.uz

Submission #881802

# Submission time Handle Problem Language Result Execution time Memory
881802 2023-12-02T02:26:40 Z HA_Blue2809 Building Bridges (CEOI17_building) C++14
100 / 100
 52 ms 73348 KB 
// 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;
}

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

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 67932 KB Output is correct
2 Correct 10 ms 67932 KB Output is correct
3 Correct 11 ms 67852 KB Output is correct
4 Correct 11 ms 67932 KB Output is correct
5 Correct 11 ms 67932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 73040 KB Output is correct
2 Correct 44 ms 73200 KB Output is correct
3 Correct 44 ms 73044 KB Output is correct
4 Correct 42 ms 72896 KB Output is correct
5 Correct 37 ms 73032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 67932 KB Output is correct
2 Correct 10 ms 67932 KB Output is correct
3 Correct 11 ms 67852 KB Output is correct
4 Correct 11 ms 67932 KB Output is correct
5 Correct 11 ms 67932 KB Output is correct
6 Correct 43 ms 73040 KB Output is correct
7 Correct 44 ms 73200 KB Output is correct
8 Correct 44 ms 73044 KB Output is correct
9 Correct 42 ms 72896 KB Output is correct
10 Correct 37 ms 73032 KB Output is correct
11 Correct 51 ms 73348 KB Output is correct
12 Correct 52 ms 73192 KB Output is correct
13 Correct 46 ms 73080 KB Output is correct
14 Correct 50 ms 73276 KB Output is correct
15 Correct 37 ms 73052 KB Output is correct
16 Correct 38 ms 73052 KB Output is correct
17 Correct 38 ms 73020 KB Output is correct
18 Correct 31 ms 73044 KB Output is correct