Submission #870452

#	Time	Username	Problem	Language	Result	Execution time	Memory
870452		LeVanThuc	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	315 ms	755280 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef thuc
    freopen("input.INP","r",stdin);
    freopen("output.OUT","w",stdout);
#else

#endif
}
const ll N=400;
ll f[N][N][N][3],n;
vector<ll> vt[3];
ll lg[4][4][N+2][N+2];
string s;
void solve(ll x,ll y)
{
    for(int i=0;i<vt[x].size();i++)
    {
        for(int j=0;j<=vt[y].size();j++)
        {
            if(j>0)
            lg[x][y][i][j]+=(vt[x][i]>vt[y][j-1]);
            lg[x][y][i][j+1]+=lg[x][y][i][j];
        }
    }
}
ll dp(ll i,ll j,ll k,ll pre)
{
    if(i==vt[0].size()&&j==vt[1].size()&&k==vt[2].size()) return 0;
    ll &res=f[i][j][k][pre];
    if(res!=-1) return res;
    res=1e9;
    if(pre!=0&&i<vt[0].size())
    {
        minimize(res,dp(i+1,j,k,0)+vt[0][i]-i-lg[0][1][i][j]-lg[0][2][i][k]);
    }
    if(pre!=1&&j<vt[1].size())
    {
        minimize(res,dp(i,j+1,k,1)+vt[1][j]-j-lg[1][0][j][i]-lg[1][2][j][k]);
    }
    if(pre!=2&&k<vt[2].size())
    {
        minimize(res,dp(i,j,k+1,2)+vt[2][k]-k-lg[2][0][k][i]-lg[2][1][k][j]);
    }
    return res;
}
int main()
{
    online();
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R') vt[0].push_back(i);
        if(s[i]=='G') vt[1].push_back(i);
        if(s[i]=='Y') vt[2].push_back(i);
    }
    solve(0,1);
    solve(0,2);
    solve(1,0);
    solve(1,2);
    solve(2,0);
    solve(2,1);
    memset(f,-1,sizeof f);
    ll z=min(dp(0,0,0,0),min(dp(0,0,0,1),dp(0,0,0,2)));
    if(z>=1e9)
    {
        z=-1;
    }
    cout<<z;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void solve(int, int)':
joi2019_ho_t3.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<vt[x].size();i++)
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int j=0;j<=vt[y].size();j++)
      |                     ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int dp(int, int, int, int)':
joi2019_ho_t3.cpp:62:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(i==vt[0].size()&&j==vt[1].size()&&k==vt[2].size()) return 0;
      |        ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(i==vt[0].size()&&j==vt[1].size()&&k==vt[2].size()) return 0;
      |                         ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:62:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(i==vt[0].size()&&j==vt[1].size()&&k==vt[2].size()) return 0;
      |                                          ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     if(pre!=0&&i<vt[0].size())
      |                ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     if(pre!=1&&j<vt[1].size())
      |                ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if(pre!=2&&k<vt[2].size())
      |                ~^~~~~~~~~~~~~

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