QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242266#7051. Largest Common Submatrixtriplem5dsWA 1ms5700kbC++232.6kb2023-11-07 04:38:312023-11-07 04:38:32

Judging History

你现在查看的是最新测评结果

  • [2023-11-07 04:38:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5700kb
  • [2023-11-07 04:38:31]
  • 提交

answer

/// Msaa el 5ra
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 3e5 + 5, A = 26, LG = 19, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;
int mxOnes[1005][1005];
int n, m;
int solve(vector<int> vec) {
  int n = vec.size();
  vector<int> lft(n, -1), rt(n, n), stk;
  for (int i = 0; i < vec.size(); i++) {
    while (stk.size() && vec[i] <= vec[stk.back()])
      stk.pop_back();
    if (!stk.empty())lft[i] = stk.back();
  }
  stk.clear();
  int ans = 0;
  for (int i = vec.size() - 1; i >= 0; --i) {
    while (stk.size() && vec[i] <= vec[stk.back()])
      stk.pop_back();
    if (!stk.empty())rt[i] = stk.back();
    ans = max(ans, (rt[i] - lft[i] - 1) * vec[i]);
  }
  return ans;
}
void doWork() {
  cin >> n >> m;
  map<ii, vector<ii>> go;
  vector<ii> cell1(n * m + 1), cell2(n * m + 1);
  f(i, 1, n + 1) {
    f(j, 1, m + 1) {
      int x;
      cin >> x;
      cell1[x] = ii(i, j);
    }
  }
  f(i, 1, n + 1) {
    f(j, 1, m + 1) {
      int x;
      cin >> x;
      cell2[x] = ii(i, j);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n * m; i++) {
    int dx = cell1[i].F - cell2[i].F;
    int dy = cell1[i].S - cell2[i].S;
    go[ii(dx, dy)].push_back(cell1[i]);
  }
  for (auto& it : go) {
    auto& vp = it.S;
    sort(all(vp));
    for (auto& p : vp) {
      mxOnes[p.F][p.S] = 1 + mxOnes[p.F - 1][p.S];
    }
    for (int i = 0, j = 0; i < vp.size(); i = j) {
      vector<int> vec;
      for (;j < vp.size() && vp[i].F == vp[j].F && (j == i || (vp[j].S == vp[j - 1].S + 1)); j++) {
        vec.push_back(mxOnes[vp[j].F][vp[j].S]);
      }
      ans = max(ans, solve(vec));
    }
    for (auto& p : vp) {
      mxOnes[p.F][p.S] = 0;
    }
  }
  cout << ans << endl;

}

int32_t main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#endif
  int t = 1;
  // cin >> t;
  while (t--) {
    doWork();
  }
}

// -Wl,--stack,1078749825

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

3 4
5 6 7 8
1 2 3 4
9 10 11 12
5 6 8 7
1 2 4 3
12 11 10 9

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10 10
13 2 57 50 1 28 37 87 30 46
66 47 33 69 83 52 97 55 91 18
9 48 23 35 98 8 7 95 90 5
3 53 43 36 96 59 26 4 70 17
71 100 15 94 25 72 84 89 21 73
64 34 22 29 42 92 85 78 86 62
99 79 67 11 6 19 24 51 77 74
75 16 88 44 93 39 41 82 56 65
12 40 63 54 10 60 32 45 20 80
49 61 76 14 81 68 27 31 58 38
13...

output:

100

result:

ok 1 number(s): "100"

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5700kb

input:

10 10
6 48 98 83 7 56 22 49 61 34
8 87 91 100 16 17 86 24 9 23
94 50 81 59 51 21 52 20 33 25
73 1 70 45 36 31 88 90 12 69
64 57 60 5 85 29 37 96 92 41
89 67 79 84 35 68 46 18 38 63
27 55 65 95 11 43 47 72 80 66
75 39 58 62 77 53 15 40 3 71
32 82 10 99 44 2 30 76 74 28
19 78 13 97 26 42 54 14 4 93
6 ...

output:

100

result:

wrong answer 1st numbers differ - expected: '80', found: '100'