Advertisement
Guest User

Untitled

a guest
Jul 18th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.04 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <experimental/set>
  3. int arr[3000][3000], brr[3000][3000];
  4.  
  5. int main() {
  6.     int n, m, a, b;
  7.     std::cin >> n >> m >> a >> b;
  8.     long long g, x, y, z;
  9.     std::cin >> g >> x >> y >> z;
  10.     x %= z, y %= z;
  11.     const bool bigTest = (std::max(a, b) > 150 || a * b > 500) && x > 1;
  12.     const int bigConst = 1e9 * 0.006;
  13.     /*
  14.         With great probability in the area of a * b
  15.         there is a value smaller than bigConst
  16.     */
  17.     const int UNREACHABLE_VALUE = 1e9 + 1;
  18.     for (int i=0; i<n; i++) {
  19.         for (int j=0; j < m; j++) {
  20.             arr[i][j] = g;
  21.             if (bigTest && arr[i][j] > bigConst) {
  22.                 arr[i][j] = UNREACHABLE_VALUE;
  23.             }  
  24.             g = (g * x + y) % z;
  25.         }
  26.     }
  27.     int64_t answer = 0;
  28.     for (int i = 0; i < n; i++) {
  29.         std::experimental::pmr::multiset<int> st;
  30.         for (int j = 0; j < b - 1; j++) {
  31.             if (arr[i][j] != UNREACHABLE_VALUE) {
  32.                 st.insert(arr[i][j]);
  33.             }
  34.         }
  35.         for (int j = b - 1; j < m; j++) {
  36.             if (arr[i][j] != UNREACHABLE_VALUE) {
  37.                 st.insert(arr[i][j]);
  38.             }
  39.            
  40.             brr[i][j - b + 1] = *st.begin();
  41.            
  42.             if (arr[i][j - b + 1] != UNREACHABLE_VALUE) {
  43.                 st.erase(st.find(arr[i][j - b + 1]));
  44.             }
  45.         }
  46.     }
  47.  
  48.     for (int j = 0; j < m - b + 1; j++) {
  49.         std::experimental::pmr::multiset<int> st;
  50.         for (int i = 0; i < a - 1; i++) {
  51.             if (brr[i][j] != UNREACHABLE_VALUE) {
  52.                 st.insert(brr[i][j]);
  53.             }
  54.         }
  55.         for (int i = a - 1; i < n; i++) {
  56.             if (brr[i][j] != UNREACHABLE_VALUE) {
  57.                 st.insert(brr[i][j]);
  58.             }
  59.            
  60.             answer += *st.begin();
  61.            
  62.             if (brr[i - a + 1][j] != UNREACHABLE_VALUE)  {
  63.                 st.erase(st.find(brr[i - a + 1][j]));
  64.             }
  65.         }
  66.     }
  67.     std::cout << answer;
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement