結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
![]() |
提出日時 | 2023-10-13 21:42:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 398 ms / 2,000 ms |
コード長 | 2,838 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 118,304 KB |
最終ジャッジ日時 | 2025-02-17 07:11:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <deque>#include <set>#include <map>#include <tuple>#include <cmath>#include <numeric>#include <functional>#include <cassert>#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }using namespace std;typedef long long ll;template<typename T>vector<vector<T>> vec2d(int n, int m, T v){return vector<vector<T>>(n, vector<T>(m, v));}template<typename T>vector<vector<vector<T>>> vec3d(int n, int m, int k, T v){return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, v)));}template<typename T>void print_vector(vector<T> v, char delimiter=' '){if(v.empty()) {cout << endl;return;}for(int i = 0; i+1 < v.size(); i++) cout << v[i] << delimiter;cout << v.back() << endl;}void solve(){int n; ll m; cin >> n >> m;vector<ll> l(n), r(n);for(int i = 0; i < n; i++) cin >> l[i];for(int i = 0; i < n; i++) cin >> r[i];ll l_sum = accumulate(l.begin(), l.end(), 0ll);ll r_sum = accumulate(r.begin(), r.end(), 0ll);if(l_sum > m || r_sum < m){cout << -1 << endl;return;}auto judge = [&](ll x){ll sum = 0;for(int i = 0; i < n; i++){if(x > r[i]){sum += r[i]-l[i];}else if(x < l[i]){sum += 0;}else{sum += x-l[i];}}return sum <= (m-l_sum);};ll lb = 0, rb = 1e10;while(rb-lb > 1){ll x = (lb+rb)/2;if(judge(x)) lb = x;else rb = x;}ll rem = m-l_sum;vector<ll> cnt(n);for(int i = 0; i < n; i++){if(lb > r[i]){cnt[i] = r[i];rem -= r[i]-l[i];}else if(lb < l[i]){cnt[i] = l[i];}else{ll p = lb-l[i];if(p <= rem){cnt[i] = lb;rem -= p;}else{cnt[i] = l[i]+rem;rem = 0;}}}for(int i = 0; i < n && rem > 0; i++){if(cnt[i] == lb && r[i] >= lb+1){cnt[i]++;rem--;}}ll ans = m*m;for(int i = 0; i < n; i++){ans -= cnt[i]*cnt[i];}ans /= 2;cout << ans << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;int t; cin >> t;while(t--) solve();}