fork(3) download
copy 
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30. #define SZ(S) ((int) ((S).size()))
  31.  
  32. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  33. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  34. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  35.  
  36. const int MN = 1011;
  37. const int oo = MN * MN;
  38. const int MOD = 1000000007;
  39. int n;
  40. char a[MN][MN];
  41. pair<int,int> f[MN][MN], g[MN][MN];
  42.  
  43. void update(pair<int,int> &f, pair<int,int> val, char c) {
  44.     int now = val.first + ((c == 'C') ? 1 : 0);
  45.     if (f.first < now) {
  46.         f.first = now;
  47.         f.second = val.second;
  48.     }
  49.     else if (f.first == now) {
  50.         f.second = (f.second + val.second) % MOD;
  51.     }
  52. }
  53.  
  54. int main() {
  55.     ios :: sync_with_stdio(false); cin.tie(NULL);
  56.     cout << (fixed) << setprecision(6);
  57.     while (cin >> n) {
  58.         FOR(i,1,n) FOR(j,1,n) cin >> a[i][j];
  59.         FOR(i,0,n+1) FOR(j,0,n+1) f[i][j] = g[i][j] = make_pair(-oo, 0);
  60.  
  61.         FOR(i,1,n) FOR(j,1,n) {
  62.             if (i == 1 && j == 1) {
  63.                 if (a[i][j] == 'C') f[i][j] = make_pair(1, 1);
  64.                 else f[i][j] = make_pair(0, 1);
  65.             }
  66.             else {
  67.                 update(f[i][j], f[i-1][j], a[i][j]);
  68.                 update(f[i][j], f[i][j-1], a[i][j]);
  69.             }
  70.         }
  71.         FORD(i,n,1) FORD(j,n,1) {
  72.             if (i == n && j == n) {
  73.                 if (a[i][j] == 'C') g[i][j] = make_pair(1, 1);
  74.                 else g[i][j] = make_pair(0, 1);
  75.             }
  76.             else {
  77.                 update(g[i][j], g[i+1][j], a[i][j]);
  78.                 update(g[i][j], g[i][j+1], a[i][j]);
  79.             }
  80.         }
  81.  
  82.         int q; cin >> q;
  83.         while (q--) {
  84.             int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
  85.             ++r1; ++c1; ++r2; ++c2;
  86.  
  87.             if (r1 > r2) swap(r1, r2);
  88.             if (c1 > c2) swap(c1, c2);
  89.  
  90.             pair<int,int> res = make_pair(0, 0);
  91.             FOR(i,r2+1,n) {
  92.                 pair<int,int> cur = make_pair(f[i][c1-1].first + g[i][c1].first,
  93.                         f[i][c1-1].second * (long long) g[i][c1].second % MOD);
  94.                 update(res, cur, 0);
  95.             }
  96.             FOR(j,c2+1,n) {
  97.                 pair<int,int> cur = make_pair(f[r1-1][j].first + g[r1][j].first,
  98.                         f[r1-1][j].second * (long long) g[r1][j].second % MOD);
  99.                 update(res, cur, 0);
  100.             }
  101.             cout << res.first << ' ' << res.second << "\n";
  102.         }
  103.     }
  104.     return 0;
  105. }
  106.  
  107.  
Success #stdin #stdout 0.01s 20408KB
comments (?)
stdin
copy 
6
C...CC
CC..C.
..C...
CCC.C.
CCC.CC
CC...C
3
2 2 2 2
1 0 4 2
4 4 5 5
stdout
copy 
9 7
7 1
0 0
https://ideone.com/cIDKGP
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!