oj.uz

Submission #97765

# Submission time Handle Problem Language Result Execution time Memory
97765 2019-02-18T10:59:33 Z Bodo171 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 3 ms 384 KB 
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=405;
int dp[2][nmax][nmax][3];
int ap[3],nr[3];
int p[3][nmax][3],a[3][nmax];
int n,i,j,k,use,oth,ch,nxt,ans;
string s;
int norm(char c)
{
    if(c=='R') return 0;
    if(c=='G') return 1;
    return 2;
}
int actual_pos(int wh)
{
   int ret=a[wh][ap[wh]];
   for(int oth=0;oth<3;oth++)
     if(oth!=wh)
        ret+=max(0,ap[oth]-p[wh][ap[wh]][oth]);
   return ret;
}
void prp(int &a,int b)
{
    a=min(a,b);
}
int main()
{
    freopen("data.in","r",stdin);
    cin>>n;
    cin>>s;s=" "+s;
    for(i=1;i<=n;i++)
        a[norm(s[i])][++nr[norm(s[i])]]=i;
    for(i=0;i<3;i++)
        for(j=1;j<=nr[i];j++)
           for(oth=0;oth<3;oth++)
    {
        while(p[i][j][oth]<=nr[oth]&&a[oth][p[i][j][oth]]<a[i][j])
            p[i][j][oth]++;
        p[i][j][oth]--;
    }
    for(i=0;i<2;i++)
        for(j=0;j<=n;j++)
            for(k=0;k<=n;k++)
                for(ch=0;ch<3;ch++)
                  dp[i][j][k][ch]=(1<<30);
    for(i=0;i<3;i++)
        dp[0][0][0][i]=0;
    for(i=1;i<=n;i++)
    {
        use=1-use;
        for(j=0;j<=i;j++)
            for(k=0;k<=i-j;k++)
                for(ch=0;ch<3;ch++)
        {
            ap[0]=j;ap[1]=k;ap[2]=i-j-k;
            for(nxt=0;nxt<3;nxt++)
                if(nxt!=ch&&ap[nxt]<nr[nxt])
            {
                ap[nxt]++;
                prp(dp[use][ap[0]][ap[1]][nxt],dp[1-use][j][k][ch]+actual_pos(nxt)-i);
                ap[nxt]--;
            }
        }
        for(j=0;j<=i;j++)
            for(k=0;k<=i-j;k++)
                for(ch=0;ch<3;ch++)
        {

           dp[1-use][j][k][ch]=(1<<30);
        }
    }
    ans=(1<<30);
    for(i=0;i<3;i++)
        ans=min(ans,dp[use][nr[0]][nr[1]][i]);
    if(ans==(1<<30)) ans=-1;
    cout<<ans;
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("data.in","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -