# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
643725 | 2022-09-22T19:37:54 Z | Cyber_Wolf | Miners (IOI07_miners) | C++14 | 1500 ms | 996 KB |
// Problem: P4 - Miners // Contest: DMOJ - IOI '07 // URL: https://dmoj.ca/problem/ioi07p4 // Memory Limit: 16 MB // Time Limit: 750 ms // // Powered by CP Editor (https://cpeditor.org) #include <bits/stdc++.h> using namespace std; #define lg int #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const lg N = 1e5+5; //lg dp[N][256]; lg n; string s; vector<lg> v(N); // lg solve(lg idx, lg bit) // { // if(idx == n) // { // return 0; // } // auto &ret = dp[idx][bit]; // if(~ret) return ret; // lg x = ((bit/64)&3), y = ((bit/16)&3), a = ((bit/4)&3), b = (bit&3); // set<lg> se1; // if(v[idx] != 3) se1.insert(v[idx]); // if(x != 3) se1.insert(x); // if(y != 3) se1.insert(y); // set<lg> se2; // if(v[idx] != 3) se2.insert(v[idx]); // if(a != 3) se2.insert(a); // if(b != 3) se2.insert(b); // lg ch1 = solve(idx+1, v[idx]*64+x*16+a*4+b)+se1.size(); // lg ch2 = solve(idx+1, x*64+y*16+v[idx]*4+a)+se2.size(); // return ret = max(ch1, ch2); // } int main() { fastio; cin >> n >> s; for(int i = 0; i < n; i++) { if(s[i] == 'M') v[i] = 1; if(s[i] == 'B') v[i] = 2; } vector<lg> dp(256, LLONG_MIN); dp[255] = 0; for(int i = 0; i < n; i++) { vector<lg> new_dp(256, LLONG_MIN); for(int j = 0; j < 256; j++) { lg x = ((j>>6)&3), y = ((j>>4)&3), a = ((j>>2)&3), b = (j&3); set<lg> se1; if(v[i] != 3) se1.insert(v[i]); if(x != 3) se1.insert(x); if(y != 3) se1.insert(y); set<lg> se2; if(v[i] != 3) se2.insert(v[i]); if(a != 3) se2.insert(a); if(b != 3) se2.insert(b); new_dp[j] = max(dp[v[i]*64+x*16+a*4+b]+se1.size(), dp[x*64+y*16+v[i]*4+a]+se2.size()); } dp = new_dp; } cout << dp[255] << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 596 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 724 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 724 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 596 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 724 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 171 ms | 728 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 334 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 826 ms | 756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1568 ms | 860 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1588 ms | 996 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |