Advertisement
PikMike

Untitled

Oct 29th, 2016
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <algorithm>
  4. #include <functional>
  5. #include <vector>
  6. #include <string>
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <queue>
  11.  
  12. #define ft first
  13. #define sc second
  14. #define mp make_pair
  15. #define pb push_back
  16. #define all(x) (x).begin(), (x).end()
  17. #define sz(a) (int)(a).size()
  18. #define forn(i, n) for (int i = 0; i < (n); i++)
  19. #define fore(i, f, t) for (int i = (f); i < (t); i++)
  20. #define ll long long
  21. #define pii pair<int, int>
  22. #define pll pair<ll, ll>
  23.  
  24. using namespace std;
  25.  
  26. const int N = 2010;
  27. int a[N][N], cnt[N];
  28. ll sum[N];
  29.  
  30.  
  31. int main(){
  32. #ifdef _DEBUG
  33.     freopen("input.txt", "r", stdin);
  34.     freopen("output.txt", "w", stdout);
  35. #endif
  36.     int n, k;
  37.     scanf("%d%d", &n, &k);
  38.     forn(i, n - 1)
  39.         fore(j, i + 1, n){
  40.             scanf("%d", &a[i][j]);
  41.             a[j][i] = a[i][j];
  42.             if (a[i][j] != -1){
  43.                 cnt[i]++;
  44.                 cnt[j]++;
  45.             }
  46.         }
  47.  
  48.     forn(i, n)
  49.         forn(j, n)
  50.             sum[i] += max(a[i][j], 0);
  51.  
  52.     ll ans = 0, m = 0;
  53.     forn(i, n)
  54.         if (cnt[i] >= k){
  55.             ans += sum[i] * max(1ll, 1ll * (cnt[i] - k) * (cnt[i] - k + 1) / 2);
  56.             m += 1ll * (cnt[i] - k + 1) * (cnt[i] - k + 2) / 2;
  57.         }
  58.     if (m == 0)
  59.         printf("0\n");
  60.     else
  61.         printf("%I64d\n", ans / m);
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement