oj.uz

Submission #882888

# Submission time Handle Problem Language Result Execution time Memory
882888 2023-12-04T04:37:06 Z Matjaz Miners (IOI07_miners) C++14
100 / 100
 637 ms 110720 KB 
//
//  MinersIOI2007.cpp
//  
//
//  Created by Matjaz Leonardis on 04/12/2023.
//

#include <iostream>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

// Trying all the different Miners solutions

int N;
string food;
vector<int> f;

int dp[100005][16][16];

int product(int state, int shipment){
    
    vector<int> shipments;
    shipments.push_back(shipment);
    shipments.push_back(state % 4);
    shipments.push_back(state / 4);
    
    bool one = false, two= false, three=false;
    
    for (int i=0;i<shipments.size();i++){
        if (shipments[i] == 1) one = true;
        if (shipments[i] == 2) two = true;
        if (shipments[i] == 3) three = true;
    }
    
    return one + two + three;
    
}

int coal(int x, int mine1, int mine2){
    if (x >= N) return 0;
    if (dp[x][mine1][mine2] != -1) return dp[x][mine1][mine2];
    
    
    int tomine1 = product(mine1, f[x]) + coal(x + 1, mine1 / 4 + 4 * f[x], mine2);
    int tomine2 = product(mine2, f[x]) + coal(x + 1, mine1, mine2 / 4 + 4 * f[x]);
    
    return dp[x][mine1][mine2] = max(tomine1, tomine2);
    
}


int main(){
    
    memset(dp, -1, sizeof(dp));
    
    cin >> N;
    cin >> food;
    
    f.assign(N, 0);
    for (int i=0;i<N;i++){
        if (food[i] == 'B') f[i] = 1;
        if (food[i] == 'M') f[i] = 2;
        if (food[i] == 'F') f[i] = 3;
    }
    
    
    cout << coal(0,0,0) << endl;
    
    return 0;
}

Compilation message

miners.cpp: In function 'int product(int, int)':
miners.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i=0;i<shipments.size();i++){
      |                  ~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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