Submission #66765474

Source Code Expand

#line 2 "Library/Template.hpp"

/**
 * @file Template.hpp
 * @author log K (lX57)
 * @brief Template - テンプレート
 * @version 1.10
 * @date 2025-03-16
 */

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 12 "Library/Template.hpp"

inline bool YnPrint(bool flag){cout << (flag ? "Yes" : "No") << '\n'; return flag;}
inline bool YNPrint(bool flag){cout << (flag ? "YES" : "NO") << '\n'; return flag;}
template<typename Container>
inline void Sort(Container &container){sort(container.begin(), container.end());}
template<typename Container>
inline void ReverseSort(Container &container){sort(container.rbegin(), container.rend());}
template<typename Container>
inline void Reverse(Container &container){reverse(container.begin(), container.end());}
template<typename Value>
inline int PopCount(const Value &value){return __builtin_popcount(value);}
template<typename Value>
inline Value Floor(Value numerator, Value denominator){if(denominator < 0) numerator *= -1, denominator *= -1; return numerator < 0 ? (numerator + 1) / denominator - 1 : numerator / denominator;}
template<typename Value>
inline Value Ceil(Value numerator, Value denominator){if(denominator < 0) numerator *= -1, denominator *= -1; return numerator > 0 ? (numerator - 1) / denominator + 1 : numerator / denominator;}
template<typename Value>
inline int LowerBoundIndex(const vector<Value> &container, const Value &value){return distance(container.begin(), lower_bound(container.begin(), container.end(), value));}
template<typename Value>
inline int UpperBoundIndex(const vector<Value> &container, const Value &value){return distance(container.begin(), upper_bound(container.begin(), container.end(), value));}
template<typename Value>
inline bool Between(const Value &lower, const Value &x, const Value &higher){return lower <= x && x <= higher;}
template<typename Value>
inline bool InGrid(const Value &y, const Value &x, const Value &ymax, const Value &xmax){return Between(0, y, ymax - 1) && Between(0, x, xmax - 1);}
template<typename Value>
inline Value Median(const Value &a, const Value &b, const Value &c){return Between(b, a, c) || Between(c, a, b) ? a : (Between(a, b, c) || Between(c, b, a) ? b : c);}
template<typename Value>
inline Value Except(Value &src, Value &cond, Value &excp){return (src == cond ? excp : src);}

template<class Value>
bool chmin(Value &src, const Value &cmp){if(src > cmp){src = cmp; return true;} return false;}
template<class Value>
bool chmax(Value &src, const Value &cmp){if(src < cmp){src = cmp; return true;} return false;}
template<typename Value>
inline Value min(vector<Value> &v){return *min_element((v).begin(), (v).end());}
template<typename Value>
inline Value max(vector<Value> &v){return *max_element((v).begin(), (v).end());}

const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, -1, 0, 1};
const int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy8[8] = {0, -1, -1, -1, 0, 1, 1, 1};

vector<pair<int, int>> adjacent(int current_y, int current_x, int max_y, int max_x, bool dir_8 = false){
    vector<pair<int, int>> ret;
    for(int d = 0; d < 4 * (1 + dir_8); ++d){
        int next_y = current_y + (dir_8 ? dy8[d] : dy4[d]);
        int next_x = current_x + (dir_8 ? dx8[d] : dx4[d]);
        if(InGrid(next_y, next_x, max_y, max_x)){
            ret.emplace_back(next_y, next_x);
        }
    }
    return ret;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p){
    os << p.first << " " << p.second;
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p){
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &v){
    for (int i = 0; i < v.size(); ++i){
        os << v[i] << (i + 1 != v.size() ? "\n" : "");
    }
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (int i = 0; i < v.size(); ++i) is >> v[i];
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, set<T> &v){
    for (auto &u : v){
        os << u << " ";
    }
    return os;
}

template<typename T1, typename T2>
vector<pair<T1, T2>> AssembleVectorPair(vector<T1> &v1, vector<T2> &v2){
    assert(v1.size() == v2.size());
    vector<pair<T1, T2>> v;
    for(int i = 0; i < v1.size(); ++i) v.push_back({v1[i], v2[i]});
    return v;
}

template<typename T1, typename T2>
pair<vector<T1>, vector<T2>> DisassembleVectorPair(vector<pair<T1, T2>> &v){
    vector<T1> v1;
    vector<T2> v2;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return p.first;});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return p.second;});
    return {v1, v2};
}

template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3>> DisassembleVectorTuple(vector<tuple<T1, T2, T3>> &v){
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    transform(v.begin(), v.end(), back_inserter(v1), [](auto p){return get<0>(p);});
    transform(v.begin(), v.end(), back_inserter(v2), [](auto p){return get<1>(p);});
    transform(v.begin(), v.end(), back_inserter(v3), [](auto p){return get<2>(p);});
    return {v1, v2, v3};
}

template<typename T1 = int, typename T2 = T1>
pair<vector<T1>, vector<T2>> InputVectorPair(int size){
    vector<pair<T1, T2>> v(size);
    for(auto &[p, q] : v) cin >> p >> q;
    return DisassembleVectorPair(v);
}

template<typename T1 = int, typename T2 = T1, typename T3 = T1>
tuple<vector<T1>, vector<T2>, vector<T3>> InputVectorTuple(int size){
    vector<tuple<T1, T2, T3>> v(size);
    for(auto &[p, q, r] : v) cin >> p >> q >> r;
    return DisassembleVectorTuple(v);
}
#line 2 "ABC410/F.cpp"

// ===================================================================
// 
// Main Program
// 
// Contest : ABC410
// Problem : F
// Date    : 2025-06-14 20:58:57
// 
// ===================================================================

void solve(){
    int H, W; cin >> H >> W;
    vector<string> S(H); cin >> S;
    
    auto A = [&]{
        if(H <= W){
            vector ret(H + 1, vector(W + 1, 0));
            for(int i = 0; i < H; ++i){
                for(int j = 0; j < W; ++j){
                    ret[i + 1][j + 1] = (S[i][j] == '#' ? 1 : -1);
                }
            }
            return ret;
        }
        else{
            vector ret(W + 1, vector(H + 1, 0));
            for(int i = 0; i < H; ++i){
                for(int j = 0; j < W; ++j){
                    ret[j + 1][i + 1] = (S[i][j] == '#' ? 1 : -1);
                }
            }
            swap(H, W);
            return ret;
        }
    }();
    assert(H <= W);
    // cerr << A << endl;
    for(int i = 1; i <= H; ++i){
        for(int j = 1; j <= W; ++j){
            A[i][j] += A[i - 1][j];
        }
    }
    // for(int i = 1; i <= H; ++i){
    //     for(int j = 1; j <= W; ++j){
    //         A[i][j] += A[i][j - 1];
    //     }
    // }
    // cerr << A << endl;

    ll ans = 0;
    for(int t = 1; t <= H; ++t){
        for(int s = 0; s < t; ++s){
            vector<int> B(W + 1, 0);
            map<int, ll> cnt;
            cnt[0] = 1;
            for(int j = 1; j <= W; ++j){
                B[j] = A[t][j] - A[s][j];
                B[j] += B[j - 1];
                ans += cnt[B[j]];
                cnt[B[j]] += 1;
            }
            // cerr << "# s = " << s << ", t = " << t << ", B = " << B << ", cur = " << ans << endl;
        }
    }
    cout << ans << endl;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int T; cin >> T;
    while(T--)
    solve();
}

Submission Info

Submission Time
Task F - Balanced Rectangles
User lX57
Language C++ 23 (gcc 12.2)
Score 0
Code Size 8560 Byte
Status TLE
Exec Time 3313 ms
Memory 34760 KiB

Compile Error

Library/Template.hpp: In instantiation of ‘std::istream& operator>>(std::istream&, std::vector<_Tp>&) [with T = std::__cxx11::basic_string<char>; std::istream = std::basic_istream<char>]’:
ABC410/F.cpp:15:33:   required from here
Library/Template.hpp:96:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 525
Status
AC × 1
AC × 34
TLE × 9
Set Name Test Cases
Sample sample_01.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt
Case Name Status Exec Time Memory
hand_01.txt AC 112 ms 34760 KiB
hand_02.txt AC 106 ms 25856 KiB
hand_03.txt AC 25 ms 15984 KiB
hand_04.txt AC 12 ms 7008 KiB
sample_01.txt AC 1 ms 3600 KiB
test_01.txt AC 1 ms 3504 KiB
test_02.txt AC 1 ms 3520 KiB
test_03.txt AC 1 ms 3640 KiB
test_04.txt AC 1 ms 3376 KiB
test_05.txt AC 1 ms 3448 KiB
test_06.txt AC 2 ms 3592 KiB
test_07.txt AC 2 ms 3520 KiB
test_08.txt AC 3 ms 3524 KiB
test_09.txt AC 4 ms 3388 KiB
test_10.txt AC 8 ms 3596 KiB
test_11.txt AC 9 ms 3600 KiB
test_12.txt AC 50 ms 3456 KiB
test_13.txt AC 31 ms 3516 KiB
test_14.txt AC 88 ms 15156 KiB
test_15.txt AC 94 ms 19364 KiB
test_16.txt TLE 3313 ms 4816 KiB
test_17.txt TLE 3310 ms 4736 KiB
test_18.txt TLE 3310 ms 4788 KiB
test_19.txt TLE 3310 ms 4812 KiB
test_20.txt AC 50 ms 3528 KiB
test_21.txt TLE 3313 ms 4852 KiB
test_22.txt TLE 3311 ms 4708 KiB
test_23.txt TLE 3311 ms 4744 KiB
test_24.txt TLE 3311 ms 4900 KiB
test_25.txt AC 2736 ms 4484 KiB
test_26.txt AC 1441 ms 3752 KiB
test_27.txt AC 2550 ms 4860 KiB
test_28.txt AC 1142 ms 4052 KiB
test_29.txt AC 2300 ms 4236 KiB
test_30.txt AC 2173 ms 4868 KiB
test_31.txt TLE 3261 ms 4888 KiB
test_32.txt AC 1847 ms 3916 KiB
test_33.txt AC 303 ms 4692 KiB
test_34.txt AC 235 ms 4700 KiB
test_35.txt AC 341 ms 4708 KiB
test_36.txt AC 218 ms 5036 KiB
test_37.txt AC 429 ms 4620 KiB
test_38.txt AC 135 ms 4656 KiB