QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#242275#7051. Largest Common Submatrixtriplem5dsCompile Error//C++232.6kb2023-11-07 04:53:302024-11-04 16:53:40

Judging History

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

  • [2024-11-04 16:53:40]
  • 管理员手动重测本题所有获得100分的提交记录
  • [2023-11-07 04:53:30]
  • 评测
  • 测评结果:100
  • 用时:421ms
  • 内存:134800kb
  • [2023-11-07 04:53:30]
  • 提交

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.push_back(i);
  }
  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();
    stk.push_back(i);
    ans = max(ans, (rt[i] - lft[i] - 1) * vec[i]);
  }
  return ans;
}
vector<ii> go[2005][2005];
void doWork() {
  cin >> n >> m;
  vector<ii> cell1(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;
      int dx = cell1[x].F - i;
      int dy = cell1[x].S - j;
      go[dx + 1000][dy + 1000].push_back(cell1[x]);
    }
  }
  int ans = 0;
  for (int i = 0; i <= 2000; i++)
    for (int j = 0; j <= 2000; j++) {
      auto& vp = go[i][j];
      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();
  }
}

Details

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~