Submission #633393

#	Time	Username	Problem	Language	Result	Execution time	Memory
633393		andrei_boaca	Sailing Race (CEOI12_race)	C++14	5 / 100	175 ms	2712 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;
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++)
    {
        vector<int> v;
        for(int j=i;v.size()<n;)
        {
            v.push_back(j);
            dp[0][j][j]=-1e9;
            poz[j]=v.size();
            j++;
            if(j>n)
                j=1;
        }
        dp[0][i][i]=0;
        for(int j:v)
        {
            for(int k:muchii[j])
                if(poz[k]>poz[j])
                    dp[0][i][k]=max(dp[0][i][k],dp[0][i][j]+1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        vector<int> v;
        for(int j=i;v.size()<n;)
        {
            v.push_back(j);
            dp[1][j][j]=-1e9;
            poz[j]=v.size();
            j--;
            if(j<1)
                j=n;
        }
        dp[1][i][i]=0;
        for(int j:v)
        {
            for(int k:muchii[j])
                if(poz[k]>poz[j])
                    dp[1][i][k]=max(dp[1][i][k],dp[1][i][j]+1);
        }
    }
    for(int i=1;i<=n;i++)
        for(int j:muchii[i])
        {
            int maxim=0;
            for(int k=j;k!=i;)
            {
                maxim=max(maxim,dp[0][j][k]);
                k++;
                if(k>n)
                    k=1;
            }
            for(int k=j;k!=i;)
            {
                maxim=max(maxim,dp[1][j][k]);
                k--;
                if(k<1)
                    k=n;
            }
            maxim++;
            //cout<<maxim<<' ';
            if(maxim>ans)
            {
                ans=maxim;
                start=i;
            }
        }
    cout<<ans<<' '<<start;
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:25:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         for(int j=i;v.size()<n;)
      |                     ~~~~~~~~^~
race.cpp:45:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         for(int j=i;v.size()<n;)
      |                     ~~~~~~~~^~

• Subtask 1: 5 / 100