Submission #844968

#	Time	Username	Problem	Language	Result	Execution time	Memory
844968		konber	T-Covering (eJOI19_covering)	C++14	5 / 100	79 ms	4364 KiB

covering

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;

vector<vector<int>> g;
vector<pair<int, int>> special;
vector<int> c;
int N, M;
int memo[1001][2][2][2][2];

int max_or(int i, int j, int b1, int b2, int b3, int b4){
    int maximum = -1e9;
    if(!b1 && i && j && j < N-1) maximum = g[i][j] + g[i][j-1] + g[i][j+1] + g[i-1][j];
    if(!b2 && i < M-1 && j && j < N-1){
        maximum = max(maximum, g[i][j]+g[i][j+1]+g[i][j-1]+g[i+1][j]);
    }
    if(!b3 && i && i < M-1 && j){
        maximum = max(maximum, g[i][j]+g[i-1][j]+g[i+1][j]+g[i][j-1]);
    }
    if(!b4 && i && i < M-1 && j < N-1){
        maximum = max(maximum, g[i][j]+g[i+1][j]+g[i-1][j]+g[i][j+1]);
    }
    return maximum;
}

ll dp(int k, int b1, int b2, int b3, int b4){
    if(k==c.size()-1){
        //cout << max_or(c[k], special[0].first, b1, b2, b3, b4) << endl;
        return max_or(special[0].first, c[k], b1, b2, b3, b4);
    }
    if(memo[k][b1][b2][b3][b4] != -1) return memo[k][b1][b2][b3][b4];
    else{
        ll c1=-1e9, c2=-1e9, c3=-1e9, c4=-1e9;
        int j = c[k], i=special[0].first;
        if(!b1 && i && j && j < N-1) c1 = g[i][j] + g[i][j-1] + g[i][j+1] + g[i-1][j];
        if(!b2 && i < M-1 && j && j < N-1){
            c2 = g[i][j]+g[i][j+1]+g[i][j-1]+g[i+1][j];
        }
        if(!b3 && i && i < M-1 && j){
            c3 = g[i][j]+g[i-1][j]+g[i+1][j]+g[i][j-1];
        }
        if(!b4 && i && i < M-1 && j < N-1){
            c4 = g[i][j]+g[i+1][j]+g[i-1][j]+g[i][j+1];
        }
        //cout << c1 <<" "<< c2 <<" "<< c3 <<" "<< c4;
        if(c[k+1] == j+1)
            return memo[k][b1][b2][b3][b4] = dp(k+1, 1, 1, 1, 0) + c3;

        if(c[k+1] = j+2){
            ll ch1 = max(c1, max(c2, c4)) + dp(k+1, 1, 1, 1, 0);
            ll ch2 = c3 + dp(k+1, 0, 0, 0, 0);
            return memo[k][b1][b2][b3][b4] = max(ch1, ch2);
        }
        return memo[k][b1][b2][b3][b4] = max(c1, max(c2, max(c3, c4))) + dp(k+1, 0, 0, 0, 0);
    }
}

int main()
{
    scanf("%d%d", &M, &N);
    g.resize(M, vector<int>(N));
    for(int i=0; i < M; i++){
        for(int j=0; j < N; j++) scanf("%d", &g[i][j]);
    }

    int k;
    scanf("%d", &k);

    bool same_row=true, all_far=true;
    special.resize(k);
    for(int i=0; i < k; i++){
        scanf("%d%d", &special[i].first, &special[i].second);
        if(i && special[i].first != special[i-1].first) same_row=false;
        if(i && fabs(special[i].first-special[i-1].first) <= 2 && fabs(special[i].second-special[i-1].second) <= 2)
            all_far = false;
    }

    if(all_far){
        bool valid=true;
        int sum=0;
        for(int i=0; i < k; i++){
            int m = max_or(special[i].first, special[i].second, 0,0,0,0);
            if(m==-1e9){
                valid = false;
                break;
            }
            sum += m;
        }

        if(valid) printf("%d\n", sum);
        else printf("No\n");
    }
    else if(same_row){
        c.resize(k);
        for(int i=0; i < k; i++) c[i] = special[i].second;
        sort(c.begin(), c.end());

        memset(memo, -1, sizeof memo);
        ll ans = dp(0, 0, 0, 0, 0);
        if(ans < 0) printf("No\n");
        else printf("%lld\n", ans);
    }
}

Compilation message (stderr)

covering.cpp: In function 'll dp(int, int, int, int, int)':
covering.cpp:32:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if(k==c.size()-1){
      |        ~^~~~~~~~~~~~
covering.cpp:54:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |         if(c[k+1] = j+2){
covering.cpp: In function 'int main()':
covering.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d", &M, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:68:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         for(int j=0; j < N; j++) scanf("%d", &g[i][j]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~
covering.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &k);
      |     ~~~~~^~~~~~~~~~
covering.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d%d", &special[i].first, &special[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30