Submission #633404

#	Time	Username	Problem	Language	Result	Execution time	Memory
633404		andrei_boaca	Sailing Race (CEOI12_race)	C++14	0 / 100	259 ms	2544 KiB

race

#include <bits/stdc++.h>

using namespace std;
int n,c;
vector<int> muchii[505];
int dp[2][505][505]; // 0 -> cresc, 1 -> desc
int poz[505];
int ans,start=0;
bool use[505];
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        while(x!=0)
        {
            muchii[i].push_back(x);
            cin>>x;
        }
    }
    //assert(c==0);
    for(int i=1;i<=n;i++)
        dp[0][i][i]=dp[1][i][i]=0;
    for(int lg=2;lg<n;lg++)
        for(int i=1;i<=n;i++)
        {
            int dr=i;
            for(int j=1;j<=n;j++)
                use[j]=0;
            for(int cnt=1;cnt<lg;cnt++)
            {
                use[dr]=1;
                dr++;
                use[dr]=1;
                if(dr>n)
                    dr=1;
            }
            bool ok=0;
            if(i==7&&dr==5)
                ok=1;
            dp[0][i][dr]=-1e9;
            for(int j:muchii[i])
                if(use[j])
                {
                    int lft=i+1;
                    if(lft>n)
                        lft=1;
                    int rgt=j;
                    int val=dp[0][rgt][lft]+1;
                    dp[0][i][dr]=max(dp[0][i][dr],val);

                    lft=j;
                    rgt=dr;
                    val=dp[1][lft][rgt]+1;
                    dp[0][i][dr]=max(dp[0][i][dr],val);
                }
            int st=i;
            for(int j=1;j<=n;j++)
                use[j]=0;
            for(int cnt=1;cnt<lg;cnt++)
            {
                use[st]=1;
                st--;
                use[st]=1;
                if(st<1)
                    st=n;
            }
            dp[1][i][st]=-1e9;
            for(int j:muchii[i])
                if(use[j])
                {
                    int rgt=i-1;
                    if(rgt<1)
                        rgt=n;
                    int lft=j;
                    int val=dp[1][lft][rgt]+1;
                    dp[1][i][st]=max(dp[1][i][st],val);

                    rgt=j;
                    lft=st;
                    val=dp[0][rgt][lft]+1;
                    dp[1][i][st]=max(dp[1][i][st],val);
                }
            if(dp[0][i][dr]>ans)
            {
                ans=dp[0][i][dr];
                start=i;
            }
            if(dp[1][i][st]>ans)
            {
                ans=dp[1][i][st];
                start=i;
            }
        }
    cout<<ans<<' '<<start;
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:40:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   40 |             bool ok=0;
      |                  ^~

• Subtask 1: 0 / 100