Advertisement
Kambarych

SOS DP

Jan 2nd, 2025
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define For(i, n)           for(int i = 0; i < n; ++i)
  6. #define all(x)              (x).begin(),(x).end()
  7. #define rall(x)             (x).rbegin(),(x).rend()
  8. #define ls(x)               x+x+1
  9. #define rs(x)               x+x+2
  10. #define endl                '\n'
  11.  
  12. #define ld                  long double
  13. #define pii                 pair<int, int>
  14. #define vt                  vector
  15. #define ll                  long long
  16.  
  17. #define sim template < class c
  18. #define ris return * this
  19. #define dor > debug & operator <<
  20. #define eni(x) sim > typename \
  21. enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  22. sim > struct rge { c b, e; };
  23. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  24. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  25. sim > char dud(...);
  26. #define LOCAL
  27. struct debug {
  28. #ifdef LOCAL
  29. ~debug() { cerr << endl; }
  30. eni(!=) cerr << boolalpha << i; ris; }
  31. eni(==) ris << range(begin(i), end(i)); }
  32. sim, class b dor(pair < b, c > d) {
  33. ris << "(" << d.first << ", " << d.second << ")";
  34. }
  35. sim dor(rge<c> d) {
  36. *this << "[";
  37. for (auto it = d.b; it != d.e; ++it)
  38.     *this << ", " + 2 * (it == d.b) << *it;
  39. ris << "]";
  40. }
  41. #else
  42. sim dor(const c&) { ris; }
  43. #endif
  44. };
  45. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  46.  
  47. template<typename T> void read(vt<T> & a) {For(i, a.size()) cin >> a[i];}
  48. template<typename T> void read2(vt<vt<T> > & a) {For(i, a.size()) read(a[i]);}
  49. template<typename T> void print(vt<T> & a) {For(i, a.size()) cout << a[i] << " "; cout << endl;}
  50. template<typename T> void print2(vt<vt<T> > & a) {For(i, a.size()) print(a[i]);}
  51.  
  52. const int MAX = 1e9;
  53. const int MOD = 1000000007;
  54. const ll  INF = 1e18;
  55. const ld  PI  = 3.14159265358979323846;
  56.  
  57. const pair<int, int> invalid = pair(-1, -1);
  58.  
  59. void solve() {
  60.     int n, m; cin >> n >> m;
  61.     vt a = vt(n, vt (m, ' ')); read2(a);
  62.     int M = (1 << m);
  63.     vt F = vt(M, invalid);
  64.     vt A = vt(n, invalid);
  65.     For(i, n) {
  66.         int mask = 0;
  67.         int cnt = 0;
  68.         For(j, m) {
  69.             if (a[i][j] == 'N') continue;
  70.             mask |= (1 << j);
  71.             cnt++;
  72.         }
  73.         int inv_mask = (M - 1) - mask;
  74.         A[i] = pair(mask, cnt);
  75.         if (F[inv_mask].first >= cnt) continue;
  76.         F[inv_mask] = pair(cnt, i);
  77.     }
  78.     for (int b = 0; b < m; b++) {
  79.         for (int mask = 0; mask < M; mask++) {
  80.             if (mask & (1 << b)) {
  81.                 auto before = F[mask ^ (1 << b)];
  82.                 if (F[mask].first < before.first) {
  83.                     F[mask] = before;
  84.                 } else if (F[mask].first == before.first && F[mask].second > before.second) {
  85.                     F[mask] = before;
  86.                 }
  87.             }
  88.         }
  89.     }
  90.     pair<int, pii> ans = pair(-1, invalid);
  91.     for (int i = 0; i < n; i++) {
  92.         auto [mask, cnt] = A[i];
  93.         if (F[mask] == invalid) {
  94.             continue;
  95.         }
  96.         int mn = min(i, F[mask].second);
  97.         int mx = max(i, F[mask].second);
  98.         if (mn == mx) continue;
  99.         auto temp = pair(cnt + F[mask].first, pair(mn, mx));
  100.         if (ans.first > temp.first) continue;
  101.         if (ans.first < temp.first) {
  102.             ans = temp;
  103.             continue;
  104.         }
  105.         if (ans.second.first < temp.second.first) continue;
  106.         if (ans.second.first > temp.second.first) {
  107.             ans = temp;
  108.             continue;
  109.         }
  110.         if (ans.second.second > temp.second.second) {
  111.             ans = temp;
  112.         }
  113.     }
  114.     if (ans.first < m) {
  115.         cout << "No" << endl;
  116.         return;
  117.     }
  118.     cout << ans.second.first + 1 << " " << ans.second.second + 1 << endl;
  119. }
  120.  
  121. // THE SOLUTION IS ALWAYS SIMPLE
  122. // THE CODE IS ALWAYS SHORT
  123.  
  124. int main() {
  125.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  126. #ifdef DEBUG
  127.     freopen("output.txt", "w", stdout);
  128.     freopen("input.txt", "r", stdin);
  129. #endif
  130.     int T = 1;
  131.     For(t, T) solve();
  132.     return 0;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement