oj.uz

Submission #93913

# Submission time Handle Problem Language Result Execution time Memory
93913 2019-01-13T07:16:36 Z kjain_1810 Vođe (COCI17_vode) C++17
72 / 120
 3000 ms 98548 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define ind2(a, b) scanf("%d%d", &a, &b)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

using namespace std;

const int N=5e3+5;
const int MOD=1e9+7;

typedef long long ll;
typedef long double ld;

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

int solve(int i, int least)//tells if team 1 won or not
{
    if(least>=m)
        return 1-arr[i];
    if(dp[i][least]!=-1)
        return dp[i][least];
    int ret=0;
    if(arr[i])
        for(int j=least; j<=least+k-1 && j<m; j++)
            ret=max(ret, solve((i+1)%n, j+1));
    else
    {
        ret=1;
        for(int j=least; j<=least+k-1 && j<m; j++)
            ret=min(ret, solve((i+1)%n, j+1));
    }
    return dp[i][least]=ret;
}

void bottomup()
{
    for(int least=m; least>=1; least--)
    {
        for(int i=n-1; i>=0; i--)
        {
            if(least==m)
                dp[i][least]=1-arr[i];
            else
            {
                if(arr[i])
                {
                    dp[i][least]=0;
                    for(int j=least; j<=least+k-1 && j<m; j++)
                        dp[i][least]=max(dp[i][least], dp[(i+1)%n][j+1]);
                }
                else
                {
                    dp[i][least]=1;
                    for(int j=least; j<=least+k-1 && j<m; j++)
                        dp[i][least]=min(dp[i][least], dp[(i+1)%n][j+1]);
                }
            }
        }
    }
}

int main() 
{
    ind3(n, m, k);
    for(int a=0; a<n; a++)
        ind(arr[a]);
    memset(dp, -1, sizeof(dp));
    // for(int a=0; a<n; a++)
    // {
    //     int ans=solve(a, 1);
    //     printf("%d ", ans);
    // }
    bottomup();
    for(int a=0; a<n; a++)
        printf("%d ", dp[a][1]);
    printf("\n");
    return 0;
}

Compilation message

vode.cpp: In function 'int main()':
vode.cpp:9:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
vode.cpp:70:5: note: in expansion of macro 'ind3'
     ind3(n, m, k);
     ^~~~
vode.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ind(a) scanf("%d", &a)
                ~~~~~^~~~~~~~~~
vode.cpp:72:9: note: in expansion of macro 'ind'
         ind(arr[a]);
         ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 98296 KB Output is correct
2 Correct 68 ms 98424 KB Output is correct
3 Correct 72 ms 98296 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 98396 KB Output is correct
2 Correct 71 ms 98424 KB Output is correct
3 Correct 76 ms 98424 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 98296 KB Output is correct
2 Correct 77 ms 98372 KB Output is correct
3 Correct 70 ms 98296 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 98352 KB Output is correct
2 Correct 98 ms 98424 KB Output is correct
3 Correct 81 ms 98296 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 98408 KB Output is correct
2 Correct 87 ms 98472 KB Output is correct
3 Correct 108 ms 98296 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 98296 KB Output is correct
2 Correct 93 ms 98424 KB Output is correct
3 Correct 79 ms 98296 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 98424 KB Output is correct
2 Correct 795 ms 98548 KB Output is correct
3 Execution timed out 3040 ms 98424 KB Time limit exceeded

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 98420 KB Output is correct
2 Execution timed out 3072 ms 98424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 98296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 98424 KB Time limit exceeded
2 Halted 0 ms 0 KB -