結果
問題 | No.837 Noelちゃんと星々2 |
ユーザー | beet |
提出日時 | 2019-06-14 21:45:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,181 bytes |
コンパイル時間 | 2,268 ms |
コンパイル使用メモリ | 198,720 KB |
最終ジャッジ日時 | 2025-01-07 04:27:44 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct FastIO{ FastIO(){ cin.tie(0); ios::sync_with_stdio(0); } }fastio_beet; //INSERT ABOVE HERE signed main(){ Int n; cin>>n; vector<Int> ys(n); for(Int i=0;i<n;i++) cin>>ys[i]; sort(ys.begin(),ys.end()); if(ys.front()==ys.back()){ cout<<1<<endl; return 0; } // dp1: [l, r) // dp2: [r, n) vector<Int> dp1(n+1,0),dp2(n,0); { Int sum=0,res=0; for(Int i=0;i<n;i++){ sum+=ys[i]; Int j=i/2; if(~i&1) res+=ys[j]; dp1[i+1]=(ys[j]*(j+1)-res)+((sum-res)-ys[j]*(i-j)); //cout<<i<<" "<<j<<":"<<sum<<" "<<res<<":"<<dp1[i+1]<<endl; } } { Int sum=0,res=0; for(Int i=n-1;i>=0;i--){ sum+=ys[i]; Int j=i+(n-i)/2; if((n-i)&1) res+=ys[j]; dp2[i]=(ys[j]*(j-i)-(sum-res))+(res-ys[j]*(n-j)); //cout<<i<<" "<<j<<":"<<dp2[i]<<endl; } } Int ans=dp1[0]+dp2[0]; for(Int i=0;i<n;i++) chmin(ans,dp1[i]+dp2[i]); cout<<ans<<endl; return 0; }