fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/detail/standard_policies.hpp>
  3. #define FOR0(i,n) for(int i=0;i<n;i++)
  4. #define FOR(i,j,n) for(int i=j;i<n;i++)
  5. #define FORD(i,j,k) for(int i=j;i>=k;i--)
  6. #define FORA(i,a) for(auto &i : a)
  7. #define pb push_back
  8. #define mp make_pair
  9. #define ff first
  10. #define ss second
  11. #define inf 1000000000
  12. #define ninf -1000000000
  13. #define endl '\n' 
  14. #define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
  15. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  16. // Use cout.flush() for interactive problems.
  17. // Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
  18. inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
  19. inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
  20. inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
  21. inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24. typedef long long ll;
  25. typedef pair<int,int> ii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<int> vi;
  28. typedef vector<vector<int>> vvi;
  29. typedef vector<bool> vb;
  30. typedef vector<ll> vll;
  31. typedef vector<vll> vvll;
  32. typedef vector<ii> vii;
  33. typedef vector<vii> vvii;
  34. ll const M = 1000000007LL;
  35.  
  36. struct fraction {
  37.     ll num;
  38.     ll den;
  39.  
  40.     fraction(ll a, ll b) {
  41.         a %= M;
  42.         b %= M;
  43.         ll c = __gcd(a,b);
  44.         num = a/c;
  45.         den = b/c;
  46.     }
  47.  
  48.     fraction operator*(fraction other) {
  49.         return fraction((num*other.num)%M,(den*other.den)%M);
  50.     }
  51.  
  52.     fraction operator+(fraction other) {
  53.         return fraction(((num*other.den)%M + (den*other.num)%M)%M,(den*other.den)%M);
  54.     }
  55.  
  56.     fraction operator-(fraction other) {
  57.         return fraction(((num*other.den)%M - (den*other.num)%M + M)%M,(den*other.den)%M);
  58.     }
  59.  
  60.     fraction operator/(fraction other) {
  61.         return fraction((num*other.den)%M,(den*other.num)%M);
  62.     }
  63.  
  64.     bool operator<(const fraction& other) const {
  65.         if (num < other.num) return true;
  66.         else if (num == other.num) return (den < other.den);
  67.         else return false;
  68.     }
  69. };
  70.  
  71. struct custom_hash {
  72.     static uint64_t splitmix64(uint64_t x) {
  73.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  74.         x += 0x9e3779b97f4a7c15;
  75.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  76.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  77.         return x ^ (x >> 31);
  78.     }
  79.  
  80.     size_t operator()(uint64_t x) const {
  81.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  82.         return splitmix64(x + FIXED_RANDOM);
  83.     }
  84.  
  85.     size_t operator()(pair<uint64_t,uint64_t> x) const {
  86. 		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  87. 		return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
  88. 	}
  89.  
  90.     size_t operator()(fraction x) const {
  91.         return operator()(mp(x.num,x.den));
  92.     }
  93. };
  94.  
  95. inline ll modulo(ll a, ll m) {
  96.     return (a%m + m)%m;
  97. }
  98.  
  99. inline ll modInverse(ll a, ll m) { 
  100.     assert (__gcd(a,m) == 1);
  101.     ll m0 = m; 
  102.     ll y = 0, x = 1; 
  103.  
  104.     if (m == 1) 
  105.       return 0; 
  106.  
  107.     while (a > 1) {
  108.         ll q = a / m; 
  109.         ll t = m; 
  110.  
  111.         m = a % m, a = t; 
  112.         t = y; 
  113.  
  114.         y = x - q * y; 
  115.         x = t; 
  116.     } 
  117.  
  118.     if (x < 0) 
  119.        x += m0; 
  120.  
  121.     return x; 
  122. } 
  123.  
  124. inline ll modPow(ll x, ll y, ll m) { //x^y % m
  125.     if (y == 0) return 1LL;
  126.     else if (y == 1) return x;
  127.     else {
  128.         ll ans = modPow(x,y/2,m)%m;
  129.         if (y&1) {
  130.             return (((ans*ans)%m)*x)%m;
  131.         }
  132.         else {
  133.             return (ans*ans)%m;
  134.         }
  135.     }
  136. }
  137.  
  138. void solve(int tc);
  139.  
  140. enum dirs{N,E,W,S};
  141.  
  142. int main() {
  143.     fast_io
  144.  
  145.     ll t,c=1;
  146.     // t = 1;
  147.     cin >> t;
  148.     while (t--) {
  149.         solve(c);
  150.         c++;
  151.     }
  152. }
  153.  
  154. void solve(int tc) {
  155.     int R,C;
  156.     cin >> R >> C;
  157.  
  158.     ll dancers[R][C];
  159.     ii nebs[R][C][4];
  160.     ll interest_round(0);
  161.     ll total_interest(0);
  162.     FOR0(i,R) {
  163.         FOR0(j,C) {
  164.             cin >> dancers[i][j];
  165.             interest_round += dancers[i][j];
  166.             FOR0(k,4) nebs[i][j][k] = mp(-1,-1);
  167.         }
  168.     }
  169.  
  170.     list<ii> prev;
  171.     total_interest += interest_round;
  172.  
  173.     for(int i = 0; i < R; i++) {
  174.         for (int j = 0; j < C; j++) {
  175.             ll sum = 0;
  176.             ll count = 0;
  177.             if (i >= 1) {
  178.                 sum += dancers[i-1][j];
  179.                 count++;
  180.                 nebs[i][j][E] = mp(i-1,j);
  181.             }
  182.             if (i+1 <= R-1) {
  183.                 sum += dancers[i+1][j];
  184.                 count++;
  185.                 nebs[i][j][W] = mp(i+1,j);
  186.             }
  187.             if (j >= 1) {
  188.                 sum += dancers[i][j-1];
  189.                 count++;
  190.                 nebs[i][j][N] = mp(i,j-1);
  191.             }
  192.             if (j+1 <= C-1) {
  193.                 sum += dancers[i][j+1];
  194.                 count++;
  195.                 nebs[i][j][S] = mp(i,j+1);
  196.             }
  197.             if (sum > count*dancers[i][j]) {
  198.                 prev.pb(mp(i,j));
  199.             }
  200.         }
  201.     }
  202.  
  203.     while (prev.size() != 0) {
  204.         list<ii> nex;
  205.         FORA(i,prev) {
  206.             interest_round -= dancers[i.first][i.second];
  207.             for(int j = 0; j < 4; j++) {
  208.                 ii p = nebs[i.first][i.second][j];
  209.                 if (p != mp(-1,-1)) {
  210.                     nebs[p.first][p.second][3-j] = nebs[i.first][i.second][3-j];
  211.                 }
  212.             }
  213.  
  214.             for (int j = 0; j < 4; j++) {
  215.                 ii p = nebs[i.first][i.second][j];
  216.                 if (p != mp(-1,-1)) {
  217.                     ll cnt = 0;
  218.                     ll sum = 0;
  219.                     for (int k = 0; k < 4; k++) {
  220.                         ii p2 = nebs[p.first][p.second][k];
  221.                         if (p2 != mp(-1,-1)) {
  222.                             cnt++;
  223.                             sum += dancers[p2.first][p2.second];
  224.                         }
  225.                     }
  226.                     if (sum > dancers[p.first][p.second]*cnt) {
  227.                         nex.pb(p);
  228.                     }
  229.                 }
  230.             }
  231.         }
  232.         total_interest += interest_round;
  233.         prev = nex;
  234.     }
  235.     printf("Case #%d: %lld\n",tc,total_interest);
  236. }
Success #stdin #stdout 0s 4320KB
comments (?)
stdin
copy 
1
1 1
15
stdout
copy 
Case #1: 15
https://ideone.com/DyPwvC
language:
C++14 (gcc 8.3)
created:
5 years 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!