結果
問題 | No.2251 Marking Grid |
ユーザー |
|
提出日時 | 2023-03-17 21:49:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 350 ms / 3,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 821 ms |
コンパイル使用メモリ | 88,568 KB |
実行使用メモリ | 15,000 KB |
最終ジャッジ日時 | 2024-09-18 10:39:50 |
合計ジャッジ時間 | 5,031 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<atcoder/modint>#include<atcoder/dsu>using namespace std;using mint=atcoder::modint998244353;int H,W;int main(){cin>>H>>W;vector<pair<int,pair<int,int> > >A;A.reserve(H*W);for(int i=0;i<H;i++)for(int j=0;j<W;j++){int a;cin>>a;A.push_back(make_pair(a,make_pair(i,j)));}sort(A.begin(),A.end());reverse(A.begin(),A.end());atcoder::dsu uf(H+W);mint tmp=mint::raw(2).pow(H+W-1);const mint inv2=mint(1)/2;mint ans=0;for(pair<int,pair<int,int> >p:A){int i=p.second.first,j=p.second.second;if(!uf.same(i,j+H)){ans+=tmp*inv2*p.first;uf.merge(i,j+H);tmp*=inv2;}}cout<<ans.val()<<endl;}