fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug clog << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define popcle
  46. #define BIT(x, i) ((x) >> (i)) & 1
  47. #define MASK(x) ((1LL) << (x))
  48. #define want_digit(x) cout << fixed << setprecision(x);
  49. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  50. using namespace std;
  51. const int MOD = 1e9 + 7; // 998244353
  52. const int inf = 1e9;
  53. const ll INF = 1e18;
  54. const int N = 2e3;
  55.  
  56. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  57. ll random(const ll &L, const ll &R)
  58. {
  59.     return uniform_int_distribution<ll> (L, R) (rng);
  60. }
  61.  
  62. int m, n, k, x, y;
  63. ll v[N + 5][N + 5], sum_row[N + 5], sum_col[N + 5], ans, total, avg_row, avg_col, a;
  64. void solve()
  65. {
  66.     cin >> m >> n >> k;
  67.     forw (i, 1, k)
  68.     {
  69.         cin >> x >> y >> a;
  70.         v[x][y] += a;
  71.         total += a;
  72.     }
  73.  
  74.     forw (i, 1, m) forw (j, 1, n)
  75.     {
  76.         sum_row[i] += v[i][j];
  77.         sum_col[j] += v[i][j];
  78.     }
  79.  
  80.     avg_row = total / m;
  81.     forw (i, 1, m)
  82.     {
  83.         if (sum_row[i] < avg_row)
  84.         {
  85.             forw (j, 1, m)
  86.             {
  87.                 if (j == i || sum_row[j] <= avg_row) continue;
  88.                 ll add = min(sum_row[j] - avg_row, avg_row - sum_row[i]);
  89.                 ans += abs(i - j) * add;
  90.                 sum_row[i] += add;
  91.                 sum_row[j] -= add;
  92.                 if (sum_row[i] == avg_row) break;
  93.             }
  94.         }
  95.     }
  96.  
  97.     avg_col = total / n;
  98.     forw (i, 1, n)
  99.     {
  100.         if (sum_col[i] < avg_col)
  101.         {
  102.             forw (j, 1, n)
  103.             {
  104.                 if (j == i || sum_col[j] <= avg_col) continue;
  105.                 ll add = min(sum_col[j] - avg_col, avg_col - sum_col[i]);
  106.                 ans += abs(i - j) * add;
  107.                 sum_col[i] += add;
  108.                 sum_col[j] -= add;
  109.                 if (sum_col[i] == avg_col) break;
  110.             }
  111.         }
  112.     }
  113.  
  114.     cout << ans << endl;
  115. }
  116.  
  117. signed main()
  118. {
  119.     ios::sync_with_stdio(false), cin.tie(nullptr);
  120.     srand(time(NULL));
  121.     #define name "test"
  122.     /*
  123.     if (fopen(name".INP", "r"))
  124.     {
  125.         freopen(name".INP", "r", stdin);
  126.         freopen(name".OUT", "w", stdout);
  127.     }
  128.     */
  129.     int numTest = 1;
  130. //    cin >> numTest;
  131.     while (numTest--)
  132.     {
  133.         solve();
  134.     }
  135.     return 0;
  136. }
  137.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
3 3 4
1 1 4
1 1 5
3 1 3
3 2 6
stdout
copy 
18
https://ideone.com/yt0bYG
language:
C++14 (gcc 8.3)
created:
8 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!