# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1008019 | 2024-06-26T06:06:24 Z | vjudge1 | Miners (IOI07_miners) | C++17 | 935 ms | 245116 KB |
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int N = 2e5+1; int localchecker = 0; int n; string s; int dp[N][5][5][5][5]; int dis(int x, int y, int z) { set<int> cc = {x,y,z}; return cc.size(); } #define chmax(x, y) x = max(x, y); int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> s; if (n <= 20) { int sol = 0; for (int msk = 0; msk < (1 << n); msk++) { int coal = 0; vector<int> fr, sc; for (int i = 0; i < n; i++) { if (msk>>i&1) swap(fr, sc); fr.push_back(s[i]); if (fr.size() == 1) coal += 1; else if (fr.size() == 2) coal += 1+(fr[1] != fr[0]); else { set<int> cc; cc.insert(fr[fr.size()-1]); cc.insert(fr[fr.size()-2]); cc.insert(fr[fr.size()-3]); coal += cc.size(); } if (msk>>i&1) swap(fr, sc); } sol = max(sol, coal); } cerr << "Checker: " << sol << endl; localchecker = sol; } for (int i = 1; i <= n; i++) { for (int p1 = 0; p1 < 3; p1++) { for (int p2 = 0; p2 < 3; p2++) { for (int p3 = 0; p3 < 3; p3++) { for (int p4 = 0; p4 < 3; p4++) { dp[i][p1][p2][p3][p4] = -10000; } } } } } s = '#' + s; for (char &c : s) c = (c == 'M' ? 0 : (c == 'B' ? 1 : 2)); for (int i = 1; i <= n; i++) { for (int p1 = 0; p1 < 3; p1++) { for (int p2 = 0; p2 < 3; p2++) { for (int p3 = 0; p3 < 3; p3++) { for (int p4 = 0; p4 < 3; p4++) { chmax(dp[i][s[i]][p1][p3][p4], dp[i-1][p1][p2][p3][p4] + dis(s[i], p1, p2)); chmax(dp[i][p1][p2][s[i]][p3], dp[i-1][p1][p2][p3][p4] + dis(s[i], p3, p4)); } } } } } int sol = 0; for (int p1 = 0; p1 < 3; p1++) { for (int p2 = 0; p2 < 3; p2++) { for (int p3 = 0; p3 < 3; p3++) { for (int p4 = 0; p4 < 3; p4++) { chmax(sol, dp[n][p1][p2][p3][p4]); } } } } cout << sol-6; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 114 ms | 436 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 484 ms | 344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 836 ms | 452 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 4700 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 40 ms | 12888 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 81 ms | 25256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 61532 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 644 ms | 184004 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 935 ms | 245116 KB | Output is correct |