Submission #1295499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295499		kizu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	39 ms	29412 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std ;

#define is ==
#define isnt !=
#define wnsl '\n'
#define ll int

#pragma GCC optimize("unroll-oops")
#pragma GCC optimize("O3")

void chmin (ll &a, ll b) {

    a = min (a, b) ;

}

void Solve () {

    ll n ;

    cin >> n ;

    string s ;

    cin >> s ;

    ll r = 0, g = 0, y = 0 ;

    for (auto &itr : s) {

        if (itr is 'R') r ++ ;

        else if (itr is 'G') g ++ ;

        else y ++ ;

    }

    vector <ll> rc, gc, yc ;

    for (int i = 0 ; i < n ; i ++) {

        if (s [i] is 'R') rc.push_back (i) ;

        else if (s [i] is 'G') gc.push_back (i) ;

        else yc.push_back (i) ;

    }

    ll mx = n ;

    ll dpr [r + 1][mx + 1], dpg [g + 1][mx + 1], dpy [y + 1][mx + 1] ;

    for (int i = 0 ; i <= r ; i ++) {
        
        for (int j = 0 ; j <= mx ; j ++) {
            
            ll ct = 0 ;

            for (int k = 0 ; k < i ; k ++) ct += j < rc [k] ;

            dpr [i][j] = ct ;

        }

    }
    
    for (int i = 0 ; i <= g ; i ++) {
        
        for (int j = 0 ; j <= mx ; j ++) {
            
            ll ct = 0 ;

            for (int k = 0 ; k < i ; k ++) ct += j < gc [k] ;

            dpg [i][j] = ct ;

        }

    }

    for (int i = 0 ; i <= y ; i ++) {
        
        for (int j = 0 ; j <= mx ; j ++) {
            
            ll ct = 0 ;

            for (int k = 0 ; k < i ; k ++) ct += j < yc [k] ;

            dpy [i][j] = ct ;

        }

    }
    
    ll dp [r + 1][g + 1][y + 1][3] ;

    memset (dp, 0x3f3f3f3f, sizeof dp) ;

    for (int i = 0 ; i < 3 ; i ++) dp [0][0][0][i] = 0 ;
    
    for (int ir = 0 ; ir <= r ; ir ++) for (int ig = 0 ; ig <= g ; ig ++) for (int iy = 0 ; iy <= y ; iy ++) for (int k = 0 ; k < 3 ; k ++) {

        ll &s = dp [ir][ig][iy][k] ;

        if (k and ir < r) {
            
            ll pen = dpr [ir][rc [ir]] + dpg [ig][rc [ir]] + dpy [iy][rc [ir]] ;

            chmin (dp [ir + 1][ig][iy][0], s + pen) ;

        }   

        if (k isnt 1 and ig < g) {
            
            ll pen = dpr [ir][gc [ig]] + dpg [ig][gc [ig]] + dpy [iy][gc [ig]] ;

            chmin (dp [ir][ig + 1][iy][1], s + pen) ;

        }   

        if (k isnt 2 and iy < y) {
            
            ll pen = dpr [ir][yc [iy]] + dpg [ig][yc [iy]] + dpy [iy][yc [iy]] ; 
    
            chmin (dp [ir][ig][iy + 1][2], s + pen) ;

        }
        
    }

    ll mn = *min_element (dp [r][g][y], dp [r][g][y] + 3) ;

    cout << (mn > n * n * 10 ? -1 : mn) << wnsl ;

}

int main () {

    ios_base::sync_with_stdio (false) ; cin.tie (nullptr) ; cout.tie (nullptr) ;

    Solve () ;

}

Compilation message (stderr)

joi2019_ho_t3.cpp:10:35: warning: bad option '-funroll-oops' to pragma 'optimize' [-Wpragmas]
   10 | #pragma GCC optimize("unroll-oops")
      |                                   ^
joi2019_ho_t3.cpp:13:24: warning: bad option '-funroll-oops' to attribute 'optimize' [-Wattributes]
   13 | void chmin (ll &a, ll b) {
      |                        ^
joi2019_ho_t3.cpp:19:13: warning: bad option '-funroll-oops' to attribute 'optimize' [-Wattributes]
   19 | void Solve () {
      |             ^
joi2019_ho_t3.cpp:141:11: warning: bad option '-funroll-oops' to attribute 'optimize' [-Wattributes]
  141 | int main () {
      |           ^

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