結果
問題 | No.1251 絶対に間違ってはいけない最小化問題 |
ユーザー |
![]() |
提出日時 | 2020-10-09 22:24:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,224 bytes |
コンパイル時間 | 891 ms |
コンパイル使用メモリ | 101,140 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-07-20 12:28:47 |
合計ジャッジ時間 | 11,826 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <cmath> #include <map> #include <queue> #include <iomanip> #include <set> #include <tuple> #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template<class T> void chmin(T &a,const T &b){if(a>b) a=b;} template<class T> void chmax(T &a,const T &b){if(a<b) a=b;} const ll INF=1e18; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; cin>>N; vector<ll> A(N),B(N); rep(i,N) cin>>A[i]; rep(i,N) cin>>B[i]; vector<ll> X=A; sort(all(X)); X.erase(unique(all(X)),X.end()); int V=X.size(); auto calc = [&](ll x){ ll res=0; rep(i,N) res+=B[i]*abs(x-A[i]); return res; }; int low=0,high=V-1; while(low+2<high){ int lef=(low+low+high)/3; int rig=(low+high+high)/3; ll lv=calc(X[lef]); ll rv=calc(X[rig]); if(lv<rv) high=rig; else low=lef; } ll ans=INF; int mit=0; while(low<=high){ ll res=calc(X[low]); if(ans>res){ ans=res; mit=low; } low++; } cout<<X[mit]<<" "<<ans<<endl; return 0; }