Submission #633398

#	Time	Username	Problem	Language	Result	Execution time	Memory
633398		andrei_boaca	Sailing Race (CEOI12_race)	C++14	10 / 100	241 ms	2536 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;
        }
    }
    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[1][rgt][lft]+1;
                    dp[0][i][dr]=max(dp[0][i][dr],val);

                    lft=j;
                    rgt=dr;
                    val=dp[0][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[0][lft][rgt]+1;
                    dp[1][i][st]=max(dp[1][i][st],val);

                    rgt=j;
                    lft=st;
                    val=dp[1][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:39:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   39 |             bool ok=0;
      |                  ^~

• Subtask 1: 10 / 100