結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
|
提出日時 | 2023-10-13 23:58:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 560 ms / 2,000 ms |
コード長 | 957 bytes |
コンパイル時間 | 3,835 ms |
コンパイル使用メモリ | 254,292 KB |
最終ジャッジ日時 | 2025-02-17 07:41:53 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i,n) for(int i=0;i<(int)(n);i++) void solve(){ int n,m; cin>>n>>m; vector<ll> l(n),r(n); rep(i,n) cin>>l.at(i); rep(i,n) cin>>r.at(i); ll sml=0,smr=0; rep(i,n){ sml+=l.at(i); smr+=r.at(i); } if(m<sml||smr<m){ cout<<"-1\n"; return; } ll up=m; ll dw=0; while(up-dw>1){ ll md=(up+dw)/2; ll tmp=0; rep(i,n) tmp+=clamp(md,l.at(i),r.at(i)); if(tmp>m) up=md; else dw=md; } vector<ll> v(n); rep(i,n){ v.at(i)=clamp(dw,l.at(i),r.at(i)); m-=v.at(i); } vector<int> p(n); rep(i,n) p.at(i)=i; sort(p.begin(),p.end(),[&](int i,int j){ return v.at(i) < v.at(j); }); for(int i:p){ if(m<=0) break; if(v.at(i)+1<=r.at(i)){ v.at(i)++; m--; } } reverse(v.begin(),v.end()); ll sm=0; ll ans=0; rep(i,n){ ans+=sm*v.at(i); sm+=v.at(i); } cout<<ans<<"\n"; } int main(){ int t; cin>>t; rep(i,t) solve(); }