# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
432727 | 2021-06-18T12:53:18 Z | juggernaut | Miners (IOI07_miners) | C++17 | 165 ms | 512 KB |
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} typedef long long ll; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef IOI2021SG #define printl(args...)printf(args) #else #define printl(args...)((void)0) #endif char s[100005]; int dp[2][16][16]; int cost[64]; int mx; void add(char ch){ int id; if(ch=='M')id=1; if(ch=='B')id=2; if(ch=='F')id=3; for(int i=0;i<16;i++) for(int j=0;j<16;j++){ int x=i; x<<=2; x+=id; umax(dp[1][x&15][j],dp[0][i][j]+cost[x]); umax(mx,dp[1][x&15][j]); x=j; x<<=2; x+=id; umax(dp[1][i][x&15],dp[0][i][j]+cost[x]); umax(mx,dp[1][i][x&15]); } for(int i=0;i<16;i++) for(int j=0;j<16;j++){ dp[0][i][j]=dp[1][i][j]; dp[1][i][j]=-1e9; } } int main(){ for(int x=0;x<2;x++) for(int i=0;i<16;i++) for(int j=0;j<16;j++)dp[x][i][j]=-1e9; dp[0][0][0]=0; for(int i=0;i<64;i++){ int tmp=i; int x=tmp&3; tmp>>=2; int y=tmp&3; tmp>>=2; int z=tmp&3; set<int>st; st.insert(x); st.insert(y); st.insert(z); st.erase(0); cost[i]=st.size(); } int n; scanf("%d",&n); scanf("%s",&s); for(int i=0;i<n;i++)add(s[i]); printf("%d",mx); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 292 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 45 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 100 ms | 424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 165 ms | 512 KB | Output is correct |