fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define REP(i, a, b) for (int i = a; i <= b; i++)
  5. #define BACK(i, a, b) for (int i = a; i >= b; i--) 
  6. #define MOD 1000000007
  7. #define PI 4 * atan(1)
  8. #define sz(A) (int)A.size()
  9. typedef long long ll;
  10. typedef vector<int> vi;
  11. typedef pair<int, int> pii;
  12. typedef vector<long long> vll;
  13. typedef long int int32;
  14. typedef unsigned long int uint32;
  15. typedef long long int int64;
  16. typedef unsigned long long int uint64;
  17.  
  18.  
  19. void solve(int test){
  20.     int n; cin >> n;
  21.     ll k; cin >> k;
  22.     vector<ll> a(n);
  23.     REP(i,0,n-1){
  24.         cin >> a[i];
  25.     }
  26.     ll res = 0;
  27.     sort(a.begin(), a.end());
  28.     REP(i,0,n-3){
  29.         if(a[i] >= k) break;
  30.         REP(j,i+1, n-2){
  31.             if(a[i] + a[j] < k){
  32.                 auto it = lower_bound(a.begin()+j+1, a.end(), k - a[i] - a[j]);
  33.                 res += it - a.begin() - j - 1;
  34.             }
  35.         }
  36.     }
  37.     cout << res << "\n";
  38. }
  39.  
  40. int main(){
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.     cout.tie(NULL);
  44.     int typetest = 1;
  45.     if (typetest){
  46.         int t;
  47.         cin >> t;
  48.         cin.ignore();
  49.         REP(i, 1, t){
  50.             solve(i);
  51.         }
  52.     }
  53.     else solve(0);
  54. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
2
4 2
-2 0 1 3
5 12
5 1 3 4 7
stdout
copy 
2
4
https://ideone.com/RSMvGr
language:
C++14 (gcc 8.3)
created:
281 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!