結果
問題 | No.1479 Matrix Eraser |
ユーザー | Ogtsn99 |
提出日時 | 2021-04-16 21:39:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,735 bytes |
コンパイル時間 | 2,556 ms |
コンパイル使用メモリ | 225,720 KB |
実行使用メモリ | 100,720 KB |
最終ジャッジ日時 | 2023-09-15 23:54:07 |
合計ジャッジ時間 | 13,054 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
61,604 KB |
testcase_01 | AC | 24 ms
61,836 KB |
testcase_02 | WA | - |
testcase_03 | AC | 26 ms
61,476 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 82 ms
66,272 KB |
testcase_08 | AC | 110 ms
69,388 KB |
testcase_09 | AC | 196 ms
78,412 KB |
testcase_10 | AC | 350 ms
93,116 KB |
testcase_11 | AC | 223 ms
81,260 KB |
testcase_12 | AC | 92 ms
67,556 KB |
testcase_13 | AC | 109 ms
69,688 KB |
testcase_14 | AC | 96 ms
67,776 KB |
testcase_15 | AC | 57 ms
63,132 KB |
testcase_16 | AC | 101 ms
68,616 KB |
testcase_17 | AC | 424 ms
100,080 KB |
testcase_18 | AC | 423 ms
100,128 KB |
testcase_19 | AC | 413 ms
99,988 KB |
testcase_20 | AC | 434 ms
100,060 KB |
testcase_21 | AC | 426 ms
100,032 KB |
testcase_22 | AC | 421 ms
100,104 KB |
testcase_23 | AC | 431 ms
99,984 KB |
testcase_24 | AC | 424 ms
100,056 KB |
testcase_25 | AC | 419 ms
99,948 KB |
testcase_26 | AC | 412 ms
100,016 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | AC | 58 ms
66,504 KB |
testcase_38 | AC | 517 ms
97,276 KB |
testcase_39 | AC | 251 ms
100,720 KB |
testcase_40 | AC | 25 ms
61,764 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i, n) for(int (i)=0;(i)<(n);(i)++) #define rrep(i, n) for(int (i)=((n)-1);(i)>=0;(i)--) #define itn int #define miele(v) min_element(v.begin(), v.end()) #define maele(v) max_element(v.begin(), v.end()) #define SUM(v) accumulate(v.begin(), v.end(), 0LL) #define lb(a, key) lower_bound(a.begin(),a.end(),key) #define ub(a, key) upper_bound(a.begin(),a.end(),key) #define COUNT(a, key) count(a.begin(), a.end(), key) #define BITCOUNT(x) __builtin_popcount(x) #define pb push_back #define all(x) (x).begin(),(x).end() #define F first #define S second using P = pair<int, int>; using WeightedGraph = vector<vector<P>>; using UnWeightedGraph = vector<vector<int>>; using Real = long double; using Point = complex<Real>; //Point and Vector2d is the same! // p.real() or real(p) -> x軸, p.imag() or imag(p) -> y軸 using Vector2d = complex<Real>; const int MOD = 1000000007; const long long INF = 1LL << 60; const double EPS = 1e-15; const double PI = 3.14159265358979323846; template<typename T> int getIndexOfLowerBound(vector<T> &v, T x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); } template<typename T> int getIndexOfUpperBound(vector<T> &v, T x) { return upper_bound(v.begin(), v.end(), x) - v.begin(); } template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) istream &operator>>(istream &is, Point &p) { Real a, b; is >> a >> b; p = Point(a, b); return is; } template<typename T, typename U> istream &operator>>(istream &is, pair<T, U> &p_var) { is >> p_var.first >> p_var.second; return is; } template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for (T &x : vec) is >> x; return is; } template<typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { os << pair_var.first << ' ' << pair_var.second; return os; } template<typename T> ostream &operator<<(ostream &os, vector<T> &vec) { for (int i = 0; i < vec.size(); i++) os << vec[i] << ' '; return os; } template<typename T, typename U> ostream &operator<<(ostream &os, vector<pair<T, U>> &vec) { for (int i = 0; i < vec.size(); i++) os << vec[i] << '\n'; return os; } template<typename T> ostream &operator<<(ostream &os, vector<vector<T>> &df) { for (auto &vec : df) os << vec; return os; } template<typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { repi(itr, map_var) { os << *itr << ' '; itr++; itr--; } return os; } template<typename T> ostream &operator<<(ostream &os, set<T> &set_var) { repi(itr, set_var) { os << *itr << ' '; itr++; itr--; } return os; } void print() { cout << endl; } template<class Head, class... Tail> void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int h, w; cin>>h>>w; int max = 0; vector<vector<pair <int, int>>> place(500001); vector<map<int, int>> col(500001); vector<map<int, int>> row(500001); /* vector <vector<int>> a(h,vector <int>(w)); cin>>a; rep(i, h) { rep(j, w) { if(a[i][j] != 4) cout << 0 << ' '; else cout << a[i][j] << ' '; } print(); } return 0; */ for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { int a; cin>>a; chmax(max, a); place[a].pb({i, j}); col[a][j]++; row[a][i]++; } } int ans = 0; rrep(i, max+1) { if(i == 0) break; set <pair <string, int>> se; queue <pair <int, int>> rest; for (auto p : place[i]) { if(col[i][p.S] > row[i][p.F]) { se.insert({"col", p.S}); } else if(col[i][p.S] == row[i][p.F]) { if(se.count({"col", p.S}) || se.count({"row", p.F})) continue; rest.push(p); } else { se.insert({"row", p.F}); } } while(!rest.empty()) { pair <int, int> p = rest.front(); rest.pop(); if(se.count({"col", p.S}) || se.count({"row", p.F})) continue; else se.insert({"col", p.S}); } ans += se.size(); } print(ans); }