Submission #526915

#	Time	Username	Problem	Language	Result	Execution time	Memory
526915		AdamGS	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	38 ms	28652 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define pb push_back
const int LIM=407, INF=1e9+7;
vector<int>V[3];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    int ile[n][3];
    rep(i, n) {
        rep(j, 3) ile[i][j]=0;
        if(i) rep(j, 3) ile[i][j]=ile[i-1][j];
        if(s[i]=='R') {
            V[0].pb(i);
            ++ile[i][0];
        } else if(s[i]=='G') {
            V[1].pb(i);
            ++ile[i][1];
        } else {
            V[2].pb(i);
            ++ile[i][2];
        }
    }
    int dp[V[0].size()+1][V[1].size()+1][V[2].size()+1][3];
    rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) rep(i, 3) dp[a][b][c][i]=INF;
    rep(i, 3) dp[0][0][0][i]=0;
    rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) {
        if(a) {
            int koszt=max(ile[V[0][a-1]][1]-b, 0)+max(ile[V[0][a-1]][2]-c, 0);
            dp[a][b][c][0]=min(dp[a][b][c][0], dp[a-1][b][c][1]+koszt);
            dp[a][b][c][0]=min(dp[a][b][c][0], dp[a-1][b][c][2]+koszt);
        }
        if(b) {
            int koszt=max(ile[V[1][b-1]][0]-a, 0)+max(ile[V[1][b-1]][2]-c, 0);
            dp[a][b][c][1]=min(dp[a][b][c][1], dp[a][b-1][c][0]+koszt);
            dp[a][b][c][1]=min(dp[a][b][c][1], dp[a][b-1][c][2]+koszt);
        }
        if(c) {
            int koszt=max(ile[V[2][c-1]][0]-a, 0)+max(ile[V[2][c-1]][1]-b, 0);
            dp[a][b][c][2]=min(dp[a][b][c][2], dp[a][b][c-1][0]+koszt);
            dp[a][b][c][2]=min(dp[a][b][c][2], dp[a][b][c-1][1]+koszt);
        }
    }
    int ans=INF;
    rep(i, 3) ans=min(ans, dp[V[0].size()][V[1].size()][V[2].size()][i]);
    cout << (ans==INF?-1:ans) << '\n';
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:28:5: note: in expansion of macro 'rep'
   28 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) rep(i, 3) dp[a][b][c][i]=INF;
      |     ^~~
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:28:27: note: in expansion of macro 'rep'
   28 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) rep(i, 3) dp[a][b][c][i]=INF;
      |                           ^~~
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:28:49: note: in expansion of macro 'rep'
   28 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) rep(i, 3) dp[a][b][c][i]=INF;
      |                                                 ^~~
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:30:5: note: in expansion of macro 'rep'
   30 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) {
      |     ^~~
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:30:27: note: in expansion of macro 'rep'
   30 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) {
      |                           ^~~
joi2019_ho_t3.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
joi2019_ho_t3.cpp:30:49: note: in expansion of macro 'rep'
   30 |     rep(a, V[0].size()+1) rep(b, V[1].size()+1) rep(c, V[2].size()+1) {
      |                                                 ^~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25