Submission #559919

#	Time	Username	Problem	Language	Result	Execution time	Memory
559919		Huy	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	412 ms	755572 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)5e5;
const int maxN = (int)5e5 + 5;
const ll mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e17;
const ll logn = 18;
const int base = 311;
const int Block_size = 500;
const int ep = 'a';

int cu[] = {0,0,1,-1};
int cv[] = {-1,1,0,0};

int du[] = {-1,-1,+1,1};
int dv[] = {-1,+1,-1,1};

int cled[] = {6,2,5,5,4,5,6,3,7,6};

void InputFile()
{
    freopen(".inp","r",stdin);
    freopen(".out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n;
int dpr[401][401][401];
int dpg[401][401][401];
int dpy[401][401][401];
int sup_g[401];
int sup_y[401];
int sup_r[401];

vector<int> save_r,save_g,save_y;
string s;

int Cal_R(int cr,int cg,int cy)
{
    int now_pos = save_r[cr-1];
    int moved = 0;
    int k = sup_g[now_pos];
    moved += max(0,cg - k);
    k = sup_y[now_pos];
    moved += max(0,cy - k);
    return now_pos + moved - (cr + cg + cy);
    //return max(max(save_g[cg-1],save_r[cr-1]),save_y[cy-1]) - (cr + cg + cy);
}

int Cal_G(int cr,int cg,int cy)
{
    int now_pos = save_g[cg-1];
    int moved = 0;
    int k = sup_r[now_pos];
    moved += max(0,cr - k);
    k = sup_y[now_pos];
    moved += max(0,cy - k);
    return now_pos + moved - (cr + cg + cy);
    //return max(max(save_g[cg-1],save_r[cr-1]),save_y[cy-1]) - (cr + cg + cy);
}

int Cal_Y(int cr,int cg,int cy)
{
    int now_pos = save_y[cy-1];
    int moved = 0;
    int k = sup_r[now_pos];
    moved += max(0,cr - k);
    k = sup_g[now_pos];
    moved += max(0,cg - k);
    return now_pos + moved - (cr + cg + cy);
    //return max(max(save_g[cg-1],save_r[cr-1]),save_y[cy-1]) - (cr + cg + cy);
}

void Read()
{
   cin >> n >> s;
   s.insert(0,"?");
   //save_r.push_back(mod);
   //save_g.push_back(mod);
   //save_y.push_back(mod);
   for(int i = 1;i <= n;i++)
   {
       if(s[i] == 'R') save_r.push_back(i);
       if(s[i] == 'G') save_g.push_back(i);
       if(s[i] == 'Y') save_y.push_back(i);
       sup_r[i] = save_r.size();
       sup_g[i] = save_g.size();
       sup_y[i] = save_y.size();
   }
   /// init
   for(int i = 1;i <= n;i++)
   {
       for(int cr = 0;cr <= n;cr++)
       {
           for(int cg = 0;cg <= n;cg++)
           {
               dpr[i][cr][cg] = mod;
               dpg[i][cr][cg] = mod;
               dpy[i][cr][cg] = mod;
           }
       }
   }
   dpr[0][0][0] = dpg[0][0][0] = dpy[0][0][0] = 0;

   for(int i = 1;i <= n;i++)
   {
       for(int cr = 0;cr <= (int)save_r.size();cr++)
       {
           for(int cg = 0;cg <= (int)save_g.size();cg++)
           {
               int cy = i - cr - cg;
               if(cy > save_y.size()) continue;
               if(cr + cg > i) break;
               if(cr > 0)
               {
                   dpr[i][cr][cg] = min(dpg[i-1][cr-1][cg],dpy[i-1][cr-1][cg]) + Cal_R(cr,cg,cy);
               }
               if(cg > 0)
               {
                   dpg[i][cr][cg] = min(dpr[i-1][cr][cg-1],dpy[i-1][cr][cg-1]) + Cal_G(cr,cg,cy);
               }
               if(cy > 0)
               {
                   dpy[i][cr][cg] = min(dpr[i-1][cr][cg],dpg[i-1][cr][cg]) + Cal_Y(cr,cg,cy);
               }
           }
       }
   }
   int res;
   res = min(min(dpr[n][(int)save_r.size()][(int)save_g.size()],dpg[n][(int)save_r.size()][(int)save_g.size()]),dpy[n][(int)save_r.size()][(int)save_g.size()]);
   if(res >= (int)1e9) res =-1;
   cout << res;
}

void Solve()
{

}

void Debug()
{
    //Main_sub();
    //Naive();
}


int main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
joi2019_ho_t3.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      | 
joi2019_ho_t3.cpp: In function 'void Read()':
joi2019_ho_t3.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                if(cy > save_y.size()) continue;
      |                   ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void InputFile()':
joi2019_ho_t3.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen(".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen(".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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