Submission #899512

#TimeUsernameProblemLanguageResultExecution timeMemory
899512NonozeMiners (IOI07_miners)C++17
84 / 100
448 ms524288 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define int long long #define sz(x) (int)(x.size()) using namespace std; using namespace __gnu_pbds; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int n, k, m; string seq; vector<vector<vector<vector<vector<int>>>>> memo; int dp(int empl, pair<int, int> prec1, pair<int, int> prec2) { if (empl>=n) return 0; if (memo[empl][prec1.first][prec1.second][prec2.first][prec2.second]!=-1) { return memo[empl][prec1.first][prec1.second][prec2.first][prec2.second]; } int vaut=1; if (seq[empl]=='F') vaut=2; if (seq[empl]=='B') vaut=4; int s1=dp(empl+1, {prec1.second, vaut}, prec2); int s2=dp(empl+1, prec1, {prec2.second, vaut}); int mask1=vaut; mask1|=prec1.first; mask1|=prec1.second; int mask2=vaut; mask2|=prec2.first; mask2|=prec2.second; s1+=__builtin_popcount(mask1); s2+=__builtin_popcount(mask2); return memo[empl][prec1.first][prec1.second][prec2.first][prec2.second]=max(s1, s2); } void solve() { cin >> n; cin >> seq; memo.clear(); memo.resize(n, vector<vector<vector<vector<int>>>>(5, vector<vector<vector<int>>> (5, vector<vector<int>> (5, vector<int>(5, -1))))); cout << dp(0, {0, 0}, {0, 0}) << endl; return; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1;// cin >> tt; while(tt--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...