結果

問題 No.3293 Golden Cross
コンテスト
ユーザー 蜜蜂
提出日時 2025-10-03 21:50:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,827 bytes
コンパイル時間 3,489 ms
コンパイル使用メモリ 296,336 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-10-03 21:51:08
合計ジャッジ時間 13,503 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 48 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

// g++-15 1.cpp -std=c++20 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;

#include <atcoder/modint>
using namespace atcoder;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=(start);i<(ll)(end);i++)
#define per(i,start,end) for(ll i=(start);i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int h,w;
  ll k;
  cin>>h>>w>>k;
  vvll a(h,vll(w));
  rep(i,0,h)rep(j,0,w)cin>>a[i][j];
  vvi b(h,vi(w));
  rep(i,0,h)rep(j,0,w)cin>>b[i][j];

  vll sum_i(h,0),sum_j(w,0);
  rep(i,0,h){
    rep(j,0,w){
      sum_i[i]+=a[i][j];
      sum_j[j]+=a[i][j];
    }
  }
  vvi bm_i(h,vi(w)),bm_j(h,vi(w));
  rep(i,0,h){
    multiset<int> st;
    rep(j,0,w){
      st.insert(b[i][j]);
    }
    rep(j,0,w){
      st.erase(st.find(b[i][j]));
      bm_i[i][j]=*st.begin();
      st.insert(b[i][j]);
    }
  }
  rep(j,0,w){
    multiset<int> st;
    rep(i,0,h){
      st.insert(b[i][j]);
    }
    rep(i,0,h){
      st.erase(st.find(b[i][j]));
      bm_j[i][j]=*st.begin();
      st.insert(b[i][j]);
    }
  }

  auto f=[&](ll a,ll b,ll c,int s,int t,int u){
    // cout<<a<<" "<<b<<" "<<c<<" "<<s<<" "<<t<<" "<<u<<endl;
    rep(i,0,32){
      if(k&(1<<i)){
        // cout<<i<<" ";
        ll os=(1<<i)/(1<<s);
        ll ot=(1<<i)/(1<<t);
        ll ou=(1<<i)/(1<<u);
        ll z=0;
        ll ps=0,pt=0,pu=0;
        if(z<(a+os+b)*(a+os+c)){
          z=(a+os+b)*(a+os+c);
          ps=os;pt=0;pu=0;
        }
        if(z<(a+ot+b)*(a+0+c)){
          z=(a+ot+b)*(a+0+c);
          ps=0;pt=ot;pu=0;
        }
        if(z<(a+0+b)*(a+ou+c)){
          z=(a+0+b)*(a+ou+c);
          ps=0;pt=0;pu=ou;
        }
        a+=ps;b+=pt;c+=pu;
      }
    }
    // cout<<a<<" "<<b<<" "<<c<<" "<<(a+b)*(a+c)<<endl;
    return (a+b)*(a+c);
  };

  ll ans=0;
  rep(i,0,h){
    rep(j,0,w){
      ll sub=f(a[i][j],sum_j[j]-a[i][j],sum_i[i]-a[i][j],b[i][j],bm_j[i][j],bm_i[i][j]);
      ans=max(ans,sub);
    }
  }
  cout<<ans<<endl;
}
0