oj.uz

Submission #129254

# Submission time Handle Problem Language Result Execution time Memory
129254 2019-07-11T23:10:43 Z Learner99 Vođe (COCI17_vode) C++14
120 / 120
 1044 ms 192776 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1656 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 4 ms 1656 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3960 KB Output is correct
2 Correct 6 ms 3576 KB Output is correct
3 Correct 6 ms 3312 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3452 KB Output is correct
2 Correct 6 ms 3576 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 30904 KB Output is correct
2 Correct 82 ms 34040 KB Output is correct
3 Correct 976 ms 189032 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 66452 KB Output is correct
2 Correct 859 ms 172884 KB Output is correct
3 Correct 288 ms 70776 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 190436 KB Output is correct
2 Correct 9 ms 4856 KB Output is correct
3 Correct 6 ms 2936 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 191800 KB Output is correct
2 Correct 958 ms 186764 KB Output is correct
3 Correct 936 ms 192776 KB Output is correct