Submission #678642

#TimeUsernameProblemLanguageResultExecution timeMemory
678642jahsdwaijsdDango Maker (JOI18_dango_maker)C++17
13 / 100
2 ms468 KiB
/* #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") */ #include <bits/stdc++.h> #define taskname "bai3" #define all(x) x.begin(), x.end() #define ll long long #define ull unsigned ll #define ld long double #define pb push_back #define ff first #define ss second #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> using namespace std; using cd = complex<double>; const int mxN = 3e3 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, m, a[mxN][mxN]; void solve() { cin >> n >> m; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { char c; cin >> c; if(c == 'R') a[i][j] = 0; else if(c == 'G') a[i][j] = 1; else a[i][j] = 2; //cout << a[i][j] << " "; } //cout << "\n"; } int ans = 0; for(int sum = 2; sum <= n + m; ++sum) { int dp[mxN][2], cnt = 0; memset(dp, 0, sizeof dp); for(int i = 1; i <= n; ++i) { int j = sum - i; if(j > m || j < 1) continue; if(i < 3) dp[i][0] = 0; else { int tmp = 0; if(a[i][j] == 2 && a[i - 1][j] == 1 && a[i - 2][j] == 0) tmp = 1; dp[i][0] = max(dp[i - 1][0], dp[i - 3][1]) + tmp; } if(j < 3) { dp[i][1] = dp[i - 1][1]; if(i > 3) dp[i][1] = max(dp[i][1], dp[i - 3][0]); } else { int tmp = 0; if(a[i][j] == 2 && a[i][j - 1] == 1 && a[i][j - 2] == 0) tmp = 1; dp[i][1] = dp[i - 1][1] + tmp; if(i > 3) dp[i][1] = max(dp[i][1], dp[i - 3][0] + tmp); } cnt = max({cnt, dp[i][0], dp[i][1]}); } ans += cnt; } cout << ans << "\n"; } signed main() { #ifdef CDuongg freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...