oj.uz

Submission #964856

# Submission time Handle Problem Language Result Execution time Memory
964856 2024-04-17T16:35:16 Z anango Miners (IOI07_miners) C++17
100 / 100
 215 ms 205188 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int has(int a, int b, int c, int d) {
    return 64*a+16*b+4*c+d;
}
int dis(int a, int b, int c) {
    if (a==0) {
        if (b==0) {
            if (c==0) {
                return 0;
            }
            return 1;
        }
        return 1+(b!=c);
    }
    if (b==0) {
        if (a==0) {
            if (c==0) {
                return 0;
            }
            return 1;
        }
        return 1+(a!=c);
    }
    if (c==0) {
        if (b==0) {
            if (a==0) {
                return 0;
            }
            return 1;
        }
        return 1+(a!=b);
    }
    if (a==b && b==c) {
        return 1;
    }
    if (a==b || a==c || b==c) {
        return 2;
    }
    return 3;
}
signed main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int INF=1000000007;
    vector<vector<int>> dp(n+1,vector<int>(256,-INF));
    dp[0][has(0,0,0,0)] = 0;
    //store the last two shipments to mine 1 and the last two shipments to mine 2
    for (int ind=1; ind<=n; ind++) {
        int cursh = s[ind-1];
        int t=-10;
        if (cursh=='M') {
            t=1;
        }
        else if (cursh=='F') {
            t=2;
        }  
        else {
            t=3;
        }
        for (int psh1=0; psh1<4; psh1++) {
            for (int psh2=0; psh2<4; psh2++) {
                for (int psh3=0; psh3<4; psh3++) {
                    for (int psh4=0; psh4<4; psh4++) {
                        int H=dp[ind-1][has(psh1,psh2,psh3,psh4)];
                        dp[ind][has(psh2,t,psh3,psh4)] = max(dp[ind][has(psh2,t,psh3,psh4)],H+dis(psh1,psh2,t));
                        dp[ind][has(psh1,psh2,psh4,t)] = max(dp[ind][has(psh1,psh2,psh4,t)],H+dis(psh3,psh4,t));
                    }
                }
            }
        }
    }
    int ma=-1;
    for (int psh1=0; psh1<4; psh1++) {
        for (int psh2=0; psh2<4; psh2++) {
            for (int psh3=0; psh3<4; psh3++) {
                for (int psh4=0; psh4<4; psh4++) {
                   ma=max(ma,dp[n][has(psh1,psh2,psh3,psh4)]);
                }
            }
        }
    }
    cout << ma << endl;


}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10588 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20828 KB Output is correct

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 153816 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 205188 KB Output is correct