oj.uz

Submission #496573

# Submission time Handle Problem Language Result Execution time Memory
496573 2021-12-21T14:49:31 Z MohamedAliSaidane Miners (IOI07_miners) C++14
100 / 100
 1426 ms 157512 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pld> vpd;

#define pb push_back
#define popb pop_back
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
int nx[4] = {1,-1,0,0}, ny[4] = {0,0,1,-1};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}
ld dist(ld x1, ld y1, ld x2, ld y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

const int MAX_N = 1e5 + 4;
int dp[MAX_N][4][4][4][4];
int n;
vi A;
int f(int i, int x1, int x2, int y1, int y2)
{
    if(dp[i][x1][x2][y1][y2] != -1)
        return dp[i][x1][x2][y1][y2];
    unordered_set<int> u;
    unordered_set<int> v;
    if(x1 != 0)
        u.insert(x1);
    if(x2 != 0)
        u.insert(x2);
    if(y1 != 0)
        v.insert(y1);
    if(y2 != 0)
        v.insert(y2);
    u.insert(A[i]);
    v.insert(A[i]);
    if(i == n-1)
    {
        return dp[i][x1][x2][y1][y2] = max(u.size(),v.size());
    }
    int x = f(i+1,x2,A[i],y1,y2) + u.size();
    int y= f(i+1,x1,x2,y2,A[i]) + v.size();
    return dp[i][x1][x2][y1][y2] = max(x,y);
}
void solve()
{
    memset(dp,-1,sizeof(dp));
    cin >> n;
    for(int i = 0; i <n;  i ++)
    {
        char c; cin >> c;
        if(c== 'M')
            A.pb(1);
        else if(c=='F')
            A.pb(2);
        else
            A.pb(3);
    }
    cout << f(0,0,0,0,0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt  = 1;

    while(tt--)
        solve();
}

Compilation message

miners.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
miners.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100484 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100512 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100492 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 100420 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100516 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 100412 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100984 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 103108 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 106132 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 114260 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 139464 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1426 ms 157512 KB Output is correct