제출 #1249370

#제출 시각아이디문제언어결과실행 시간메모리
1249370CodeLakVNGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
36 ms29512 KiB
#include <bits/stdc++.h>
using namespace std;

#define task "main"
#define F first
#define S second
#define ii pair<int, int>
#define il pair<int, long long>
#define li pair<long long, int>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

const int MAX_N = 403;
const int INF = (int)1e9;

int n;
string s;
int cnt[3][MAX_N];
vector<int> pos[3];

void solve() {
    cin >> n >> s;
    s = "#" + s;
    FOR(i, 1, n) {
        FOR(k, 0, 2) cnt[k][i] = cnt[k][i - 1];
        int id = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
        cnt[id][i]++;
        pos[id].push_back(i);
    }

    int numR = (int)pos[0].size(), numG = (int)pos[1].size(), numY = (int)pos[2].size();
    int dp[numR + 2][numG + 2][numY + 2][3];
    FOR(r, 0, numR) FOR(g, 0, numG) FOR(y, 0, numY) FOR(col, 0, 2)
        dp[r][g][y][col] = INF;

    FOR(i, 0, 2) dp[0][0][0][i] = 0;

    FOR(i, 0, numR) FOR(j, 0, numG) FOR(k, 0, numY) FOR(x, 0, 2) {
        if (x != 0 && i < numR) {
            int cost1 = max(0, cnt[1][pos[0][i]] - j);
            int cost2 = max(0, cnt[2][pos[0][i]] - k);
            minimize(dp[i + 1][j][k][0], dp[i][j][k][x] + cost1 + cost2);
        }
        if (x != 1 && j < numG) {
            int cost0 = max(0, cnt[0][pos[1][j]] - i);
            int cost2 = max(0, cnt[2][pos[1][j]] - k);
            minimize(dp[i][j + 1][k][1], dp[i][j][k][x] + cost0 + cost2);
        }
        if (x != 2 && k < numY) {
            int cost0 = max(0, cnt[0][pos[2][k]] - i);
            int cost1 = max(0, cnt[1][pos[2][k]] - j);
            minimize(dp[i][j][k + 1][2], dp[i][j][k][x] + cost0 + cost1);
        }
    }

    int ans = INF;
    FOR(x, 0, 2) minimize(ans, dp[numR][numG][numY][x]);
    cout << (ans == INF ? -1 : ans) << "\n";
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...