oj.uz

Submission #577252

# Submission time Handle Problem Language Result Execution time Memory
577252 2022-06-14T10:51:56 Z berr T-Covering (eJOI19_covering) C++17
15 / 100
 1000 ms 900 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m; cin>>n>>m;
    int val[n][m];
    int check[n][m];

    for(int i=0; i<n; i++)
    {
        for(int l=0; l<m; l++)
            cin>>val[i][l];
    }

    int k; cin>>k;

    vector<vector<int>> groups;
    vector<array<int, 2>> ind(k);

    for(int i=0; i<k; i++)
    {
        cin>>ind[i][0]>>ind[i][1];
    }

    n--;

    int ans=0,  daa=0;
    m--;

    for(int i=0; i<(1LL<<(2*k)); i++)
    {   

        int s=0;
        int f=0;

        for(int l=2*k-1, t=0; l>0; l-=2, t++)
        {
            int x=ind[t][0];
            int y=ind[t][1];
            if(i&(1LL<<l))
            {

                if(i&(1LL<<(l-1)))
                {
                    if(x>=1&&x<=n-1&&y>=1)
                    {
                        if(check[x][y]!=i&&check[x-1][y]!=i&&check[x+1][y]!=i&&check[x][y-1]!=i)
                            s+=val[x][y]+val[x-1][y]+val[x+1][y]+val[x][y-1];
                        else
                            f=1;
                        check[x][y]=check[x-1][y]=check[x+1][y]=check[x][y-1]=i;
                   
                    }
                    else f=1;
                }

                else
                {
                    if(x>=1&&x<=n-1&&y<=m-1)
                    {
                        if(check[x][y]!=i&&check[x-1][y]!=i&&check[x+1][y]!=i&&check[x][y+1]!=i)
                            s+=val[x][y]+val[x-1][y]+val[x+1][y]+val[x][y+1];
                        else
                            f=1;
                        check[x][y]=check[x-1][y]=check[x+1][y]=check[x][y+1]=i;
                    }
                    else
                        f=1;
                }
            }
            else
            {
                if(i&(1LL<<(l-1)))
                {
                    if(y>=1&&y<=m-1&&x>=1)
                    {
                        if(check[x][y]!=i&&check[x][y-1]!=i&&check[x][y-1]!=i&&check[x-1][y]!=i)
                            s+=val[x][y]+val[x][y-1]+val[x][y+1]+val[x-1][y];
                        else
                            f=1;
                        check[x][y]=check[x][y-1]=check[x][y+1]=check[x-1][y]=i;
                    }
                    else f=1;
                }

                else
                {
                    if(y>=1&&y<=m-1&&x<=n-1)
                    {
                        if(check[x][y]!=i&&check[x][y-1]!=i&&check[x][y+1]!=i&&check[x+1][y]!=i)
                            s+=val[x][y]+val[x][y-1]+val[x][y+1]+val[x+1][y];
                        else
                            f=1;
                        check[x][y]=check[x][y-1]=check[x][y+1]=check[x+1][y]=i;
                    }
                    else f=1;
                }
            }
        }

        

        if(f==0) ans=max(ans, s), daa=1;

    }

    if(daa) cout<<ans;
    else cout<<"No\n";







}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 468 KB Output is correct
2 Execution timed out 1078 ms 852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 468 KB Output is correct
2 Execution timed out 1089 ms 724 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 468 KB Output is correct
2 Execution timed out 1087 ms 900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 212 KB Output is correct
2 Execution timed out 1090 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 296 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 110 ms 304 KB Output is correct
4 Correct 25 ms 212 KB Output is correct
5 Correct 113 ms 300 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 468 KB Output is correct
2 Execution timed out 1078 ms 852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 468 KB Output is correct
2 Execution timed out 1078 ms 852 KB Time limit exceeded
3 Halted 0 ms 0 KB -