Submission #330194

#TimeUsernameProblemLanguageResultExecution timeMemory
3301942qbingxuanDango Maker (JOI18_dango_maker)C++14
100 / 100
1154 ms90088 KiB
// __________________ // | ________________ | // || ____ || // || /\ | || // || /__\ | || // || / \ |____ || // ||________________|| // |__________________| // \###################\ // \###################\ // \ ____ \ // \_______\___\_______\ // An AC a day keeps the doctor away. #ifdef local #include <bits/extc++.h> #define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n" #define debug(args...) qqbx(#args, args) using ost = std::ostream; #define DESTL(STL, BEG, END, OUT) \ template <typename ...T> ost& operator<<(ost &O, std::STL<T...> v) { int f=0; for(auto x: v) O << (f++ ? ", " : BEG) << OUT; return O << END; } DESTL(deque, "[", "]", x); DESTL(vector, "[", "]", x); DESTL(set, "{", "}", x); DESTL(multiset, "{", "}", x); DESTL(unordered_set, "{", "}", x); DESTL(map , "{", "}", x.first << ":" << x.second); DESTL(unordered_map , "{", "}", x.first << ":" << x.second); template <typename U, typename V> ost& operator<<(ost &O, std::pair<U,V> p) { return O << '(' << p.first << ',' << p.second << ')'; } template <typename T, size_t N> ost& operator<<(ost &O, std::array<T,N> a) { int f=0; for(T x: a) O << (f++ ? ", " : "[") << x; return O << "]"; } template <typename T, size_t ...I> ost& prtuple(ost &O, T t, std::index_sequence<I...>) { return (..., (O << (I ? ", " : "(") << std::get<I>(t))), O << ")"; } template <typename ...T> ost& operator<<(ost &O, std::tuple<T...> t) { return prtuple(O, t, std::make_index_sequence<sizeof...(T)>()); } template <typename ...T> void qqbx(const char *s, T ...args) { int cnt = sizeof...(T); (std::cerr << "\033[1;32m(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\033[0m\n"))); } #else #pragma GCC optimize("Ofast") #pragma loop_opt(on) #include <bits/extc++.h> #include <bits/stdc++.h> #define debug(...) ((void)0) #define safe ((void)0) #endif // local #define all(v) begin(v),end(v) #define get_pos(v,x) int(lower_bound(begin(v),end(v),x)-begin(v)) #define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v)) #define pb emplace_back #define ff first #define ss second #define mem(v,x) memset(v,x,sizeof v) using namespace std; using namespace __gnu_pbds; typedef int64_t ll; typedef long double ld; typedef pair<ll,ll> pll; typedef pair<ld,ld> pld; template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >; template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >; template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; constexpr ld PI = acos(-1), eps = 1e-7; constexpr ll N = 3025, INF = 1e18, MOD = 1000000007, K = 14699, inf = 1e9; constexpr inline ll cdiv(ll x, ll m) { return x/m + (x%m ? (x<0) ^ (m>0) : 0); } // ceiling divide constexpr inline ll modpow(ll e,ll p,ll m=MOD) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; } int solve(vector<int> &v) { array<int,4> dp = {}; debug(v); for(int mask: v) { array<int,4> nxt = {}; if(mask & 2) { nxt[0] = max(nxt[0], dp[0] + 1); } if(mask & 1) { for(int s = 0; s < 4; s++) nxt[s >> 1 | 2] = max(nxt[s >> 1 | 2], dp[s] + 1); } for(int s = 0; s < 4; s++) nxt[s >> 1] = max(nxt[s >> 1], dp[s]); dp = nxt; } return *max_element(all(dp)); } int hori[N][N], vert[N][N]; signed main() { ios_base::sync_with_stdio(0), cin.tie(0); int n, m; cin >> n >> m; vector<string> v(n); for(int i = 0; i < n; i++) cin >> v[i]; for(int i = 0; i < n; i++) { for(int j = 0; j+3 <= m; j++) { if(v[i].substr(j, 3) == "RGW") { hori[i][j] = true; } } } for(int j = 0; j < m; j++) { for(int i = 0; i+3 <= n; i++) { string pat = v[i].substr(j, 1) + v[i+1].substr(j, 1) + v[i+2].substr(j, 1); if(pat == "RGW") { vert[i][j] = true; } } } int ans = 0; for(int s = 0; s < n+m-1; s++) { vector<int> a; for(int i = 0; i < n; i++) { int j = s - i; if(j < 0 || j >= m) continue; a.push_back(hori[i][j] * 2 + vert[i][j]); } ans += solve(a); } cout << ans << '\n'; }

Compilation message (stderr)

dango_maker.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //  \###################\
      | ^
dango_maker.cpp:35: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
   35 | #pragma loop_opt(on)
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...