結果
問題 |
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; }