結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
![]() |
提出日時 | 2023-10-13 22:12:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 622 ms / 2,000 ms |
コード長 | 1,534 bytes |
コンパイル時間 | 1,711 ms |
コンパイル使用メモリ | 171,856 KB |
実行使用メモリ | 8,584 KB |
最終ジャッジ日時 | 2024-09-15 17:56:04 |
合計ジャッジ時間 | 5,079 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef pair<ll,ll> P;typedef vector<ll> VI;typedef vector<VI> VVI;#define REP(i,n) for(int i=0;i<(n);i++)#define ALL(v) v.begin(),v.end()template<typename T> bool chmax(T& x, const T& y){return (x<y)?(x=y,true):false;};template<typename T> bool chmin(T& x, const T& y){return (x>y)?(x=y,true):false;};constexpr ll MOD=998244353;constexpr ll INF=2e18;void solve(){ll n, m; cin >> n >> m;VI l(n), r(n);REP(i,n) cin >> l[i];REP(i,n) cin >> r[i];ll lsum=0, rsum=0;REP(i,n) lsum+=l[i];REP(i,n) rsum+=r[i];if(m<lsum||rsum<m){cout << -1 << endl;return;}ll x=0, y=2e9;ll rem=m-lsum;while(y-x>1){ll z=(x+y)/2;ll sum=0;REP(i,n){if(z<l[i])sum+=l[i];else if(r[i]<z)sum+=r[i];elsesum+=z;}if(sum<=m){x=z;chmin(rem,m-sum);}elsey=z;}VI a;REP(i,n){if(x<l[i])a.push_back(l[i]);else if(r[i]<=x)a.push_back(r[i]);else{if(rem-->0)a.push_back(x+1);elsea.push_back(x);}}ll ans=0, sum=0;REP(i,n){ans+=sum*a[n-1-i];sum+=a[n-1-i];}cout << ans << endl;}int main(){int t; cin >> t;while(t--) solve();return 0;}