結果
問題 | No.1668 Grayscale |
ユーザー |
![]() |
提出日時 | 2021-05-15 19:27:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,409 ms / 4,000 ms |
コード長 | 1,319 bytes |
コンパイル時間 | 1,986 ms |
コンパイル使用メモリ | 179,628 KB |
実行使用メモリ | 92,420 KB |
最終ジャッジ日時 | 2024-12-15 08:43:34 |
合計ジャッジ時間 | 7,394 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define Pr pair<ll,ll> #define Tp tuple<ll,ll,ll> using Graph = vector<vector<Pr>>; ll mod = 998244353; int main() { //FILE *in = freopen("in/sample3.txt", "r", stdin); //FILE *out = freopen("out/sample3.txt", "w", stdout); ll H,W,N; cin >> H >> W >> N; assert(1<=H&&H<=1000&&1<=W&&W<=1000&&1<=N&&N<=H*W); ll col[H][W]; set<ll> num; rep(i,H){ rep(j,W){ cin >> col[i][j]; assert(1<=col[i][j]&&col[i][j]<=2000000000); num.insert(col[i][j]); } } assert(num.size()==N); vector<Pr> range; rep(i,H){ rep(j,W-1){ ll a = col[i][j], b = col[i][j+1]; if(a==b) continue; if(a>b) swap(a,b); range.push_back(make_pair(b,a)); } } rep(i,H-1){ rep(j,W){ ll a = col[i][j], b = col[i+1][j]; if(a==b) continue; if(a>b) swap(a,b); range.push_back(make_pair(b,a)); } } sort(range.begin(),range.end()); ll end = 0; ll ans = 1; for(auto p:range){ ll a = p.second, b = p.first; if(a>=end){ ans++; end = b; } } cout << ans << endl; }