Submission #129254

#	Time	Username	Problem	Language	Result	Execution time	Memory
129254		Learner99	Vođe (COCI17_vode)	C++14	120 / 120	1044 ms	192776 KiB

vode

#include <bits/stdc++.h>

using namespace std;


#define int long long 

#define N 5005

int n, m, k;
int dp[N][N];

int a[N];

int findans(int ind, int val)
{
        if(val > m)
                return 0;

        if(dp[ind][val]!=0)
                return dp[ind][val];

        if(val == m-1)
                return dp[ind][val]=-1;

        int x = 0, y = 0;
        int next = ind+1;
        if(next > n)
                next = 1;
        for(int i=val+1;i<=min(m-1,val+k);i++)
        {
                int temp =  findans(next, i);
                if(temp==1)
                        x=1;
                if(temp==-1)
                        y=1;
        }

        if(a[ind] == a[next] && x==1)
                return dp[ind][val] = 1;
        if(a[ind] != a[next] && y==1)
                return dp[ind][val] = 1;

        return dp[ind][val] = -1;
}

int lastNeg[N];
int lastPos[N];

void foo()
{
        for(int i=1;i<=n;i++)
        {
                dp[i][m-1]=-1;
                lastNeg[i] = m-1;
                lastPos[i] = 100000;
        }

        for(int i=m-2;i>=0;i--)
        {
                for(int j=1;j<=n;j++)
                {
                        int next = j+1;
                        if(next == n+1)
                                next = 1;
                        
                        int x = 0, y = 0;

                        int p = lastPos[next];
                        if(p!=100000 && abs(i-p) <= k)
                                x = 1;
                        
                        int q = lastNeg[next];
                        if(q!=100000 && abs(i-q) <= k)
                                y = 1;

                        if(a[j] == a[next] && x == 1)
                        {        
                                dp[j][i] = 1; 
                        }
                        else if(a[j] != a[next] && y==1)
                        {
                                dp[j][i] = 1;
                        }
                        else 
                        {
                                dp[j][i] = -1;
                        }
                }
                for(int j=1;j<=n;j++)
                {
                        if(dp[j][i] == 1)
                        {        
                                lastPos[j] = min(lastPos[j], i);
                        }
                        else
                        {
                                lastNeg[j] = min(lastNeg[j], i);
                        }
                }
        }
}


int32_t main()
{
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i];
        }

        foo();

        for(int i=1;i<=n;i++)
        {
                if(dp[i][0] < 0)
                        cout<< (a[i]+1)%2 <<" ";
                else
                        cout<< a[i] <<" ";
        }
        cout<<endl;


        return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12