oj.uz

Submission #364911

# Submission time Handle Problem Language Result Execution time Memory
364911 2021-02-10T12:36:10 Z Sparky_09 Miners (IOI07_miners) C++17
100 / 100
 84 ms 1004 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}

const int INF = 1e9;
int n, inp[100005], dp[2][4][4][4][4], ans = 0, pre[4][4][4];
string s;

int val(int x, int y, int z){
  set<int> temp; 
  if(x) temp.insert(x); 
  if(y) temp.insert(y); 
  if(z) temp.insert(z); 
  return sz(temp);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
  cin >> n >> s;
  rep(i, 1, n+1) inp[i] = (s[i-1] == 'B' ? 1 : (s[i-1] == 'M' ? 2 : 3));
  rep(i, 0, 2) rep(j, 0, 4) rep(k, 0, 4) rep(l, 0, 4) rep(m, 0, 4) dp[i][j][k][l][m] = -INF;
  rep(j, 0, 4) rep(k, 0, 4) rep(l, 0, 4) pre[j][k][l] = val(j,k,l);
  dp[0][0][0][0][0] = 0;
  rep(i, 1, n+1){
    int I = (i % 2 ? 1 : 0), c = inp[i];
    rep(j, 0, 4) rep(k, 0, 4) rep(l, 0, 4) rep(m, 0, 4){
      dp[I][j][k][m][c] = max(dp[I][j][k][m][c], dp[I^1][j][k][l][m] + pre[m][l][c]);
      dp[I][k][c][l][m] = max(dp[I][k][c][l][m], dp[I^1][j][k][l][m] + pre[j][k][c]);
      if(i == n) ans = max({ans, dp[I][k][c][l][m], dp[I][j][k][m][c]});
    }
  }
  cout << ans << '\n';
}

Compilation message

miners.cpp: In function 'void usaco(std::string)':
miners.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
miners.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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