質問編集履歴

参考にした他の人のコードを追記しました。

2020/01/08 12:12

投稿

スコア42

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -139,3 +139,143 @@
 }
 ```
+### 参考にしたコード
+```
+#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)
+using namespace std;
+typedef long long ll;
+const ll MOD=1e9+7;
+ll N,M;
+vector<ll> A;
+vector<ll> sum;
+bool judge(ll lim){
+  ll res=0;
+  int itr=0;
+  for(int i=N-1;i>=0;i--){
+    while(itr<N&&A[i]+A[itr]>=lim){
+      itr++;
+    }
+    res+=itr;
+  }
+  if(res>=M) return true;
+  else return false;
+}
+int main(){
+    cin>>N>>M;
+    A.resize(N);
+    rep(i,N) cin>>A[i];
+    sort(A.rbegin(),A.rend());
+    sum.resize(N+1,0);
+    rep(i,N) sum[i+1]=sum[i]+A[i];
+    ll ok=0,ng=(A[0]*2+1)*M;
+    while(abs(ok-ng)>1){
+        ll mid=(ok+ng)/2;
+        if(judge(mid)) ok=mid;
+        else ng=mid;
+    }
+    ll ans=0;
+    ll itr=0;
+    ll num=0;
+    for(int i=N-1;i>=0;i--){
+        while(itr<N && A[i]+A[itr]>=ok) itr++;
+        ans+=A[i]*itr+sum[itr];
+        num+=itr;
+    }
+    ans-=ok*(num-M);
+    cout<<ans<<endl;
+    return 0;
+}
+```