Submission #637611

#	Time	Username	Problem	Language	Result	Execution time	Memory
637611		ksu2009en	T-Covering (eJOI19_covering)	C++14	5 / 100	188 ms	15964 KiB

covering

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>

using namespace std;
typedef long long ll;

ll n, m;

ll check(ll x, ll y, vector<vector<ll>> &a, ll ok){
    ll res = 0;
    if(ok == 1){
        res += ((x > 0 && y > 0 && x <= n && y <= m) ? a[x][y] : -1e9);
        res += ((x - 1 > 0 && y > 0 && x - 1 <= n && y <= m) ? a[x - 1][y] : -1e9);
        res += ((x > 0 && y - 1 > 0 && x <= n && y - 1 <= m) ? a[x][y - 1] : -1e9);
        res += ((x > 0 && y + 1 > 0 && x <= n && y + 1 <= m) ? a[x][y + 1] : -1e9);
    }
    else if(ok == 2){
        res += ((x > 0 && y > 0 && x <= n && y <= m) ? a[x][y] : -1e9);
        res += ((x - 1 > 0 && y > 0 && x - 1 <= n && y <= m) ? a[x - 1][y] : -1e9);
        res += ((x + 1 > 0 && y > 0 && x + 1 <= n && y <= m) ? a[x + 1][y] : -1e9);
        res += ((x > 0 && y + 1 > 0 && x <= n && y + 1 <= m) ? a[x][y + 1] : -1e9);
    }
    else if(ok == 3){
        res += ((x > 0 && y > 0 && x <= n && y <= m) ? a[x][y] : -1e9);
        res += ((x > 0 && y - 1 > 0 && x <= n && y - 1 <= m) ? a[x][y - 1] : -1e9);
        res += ((x + 1 > 0 && y > 0 && x + 1 <= n && y <= m) ? a[x + 1][y] : -1e9);
        res += ((x > 0 && y + 1 > 0 && x <= n && y + 1 <= m) ? a[x][y + 1] : -1e9);
    }
    else if(ok == 4){
        res += ((x > 0 && y > 0 && x <= n && y <= m) ? a[x][y] : -1e9);
        res += ((x - 1 > 0 && y > 0 && x - 1 <= n && y <= m) ? a[x - 1][y] : -1e9);
        res += ((x + 1 > 0 && y > 0 && x + 1 <= n && y <= m) ? a[x + 1][y] : -1e9);
        res += ((x > 0 && y - 1 > 0 && x <= n && y - 1 <= m) ? a[x][y - 1] : -1e9);
    }
    
    return (res < 0 ? -1e9 : res);
}

int main(){
    cin >> n >> m;
    
    vector<vector<ll>>a(n + 1, vector<ll>(m + 1));
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    ll k;
    cin >> k;
    
    vector<pair<ll, ll>> d(k);
    
    for(int i = 0; i < k; i++){
        cin >> d[i].first >> d[i].second;
        d[i].first++;
        d[i].second++;
    }
    
    bool ok = false;
    
    for(int i = 0; i < k; i++)
        for(int j = i + 1; j < k; j++)
            if(abs(d[i].first - d[j].first) <= 2 && abs(d[i].second - d[j].second) <= 2)
                ok = true;
    
    vector<vector<ll>>used(n + 1, vector<ll>(m + 1));
    for(auto i: d)
        used[i.first][i.second] = 1;
     
    if(!ok){
        ll ans = 0;
        
        for(auto i: d){
            ll cnt = max({check(i.first, i.second, a, 1),
                         check(i.first, i.second, a, 2),
                         check(i.first, i.second, a, 3),
                        check(i.first, i.second, a, 4)});
            
            if(cnt == -1e9){
                cout << -1 << endl;
                return 0;
            }
            
            ans += cnt;
        }
        cout << ans << endl;
    }
    else{
        ll ans = 0;
        
        ok = false;
        
        for(int i = 0; i < k; i++)
            for(int j = i + 1; j < k; j++)
                if(abs(d[i].first - d[j].first) <= 2 && abs(d[i].second - d[j].second) <= 2){
                    
                    if(abs(d[i].first - d[j].first) == 0 && abs(d[i].second - d[j].second) == 1)
                       continue;
                       if(abs(d[i].first - d[j].first) == 1 && abs(d[i].second - d[j].second) == 0)
                          continue;
                
                    
                    ok = true;
                }
        
        if(ok){
            cout << -1 << endl;
            return 0;
        }
        
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(used[i][j]){
                    if(j + 1 <= m && used[i][j + 1]){
                        ll cnt = check(i, j, a, 2) + check(i, j + 1, a, 4);
                        if(cnt < 0){
                            cout << -1 << endl;
                            return 0;
                        }
                        
                        ans += cnt;
                    }
                    else if(i + 1 <= n && used[i + 1][j]){
                        ll cnt = check(i, j, a, 1) + check(i, j + 1, a, 3);
                        if(cnt < 0){
                            cout << -1 << endl;
                            return 0;
                        }
                        
                        ans += cnt;
                    }
                    else if((i - 1 <= 0 || !used[i - 1][j]) && (j - 1 <= 0 || !used[i][j - 1])){
                        ll cnt = max({check(i, j, a, 1),
                            check(i, j, a, 2),
                            check(i, j, a, 3),
                            check(i, j, a, 4)});
                        
                        if(cnt == -1e9){
                            cout << -1 << endl;
                            return 0;
                        }
                        
                        ans += cnt;
                    }
                }
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}
/*
 4 4
 1 1 1 1
 2 2 2 2
 1 1 2 2
 1 1 2 2
 2
 1 1
 1 2
 
 */

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:110:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  110 |                     if(abs(d[i].first - d[j].first) == 0 && abs(d[i].second - d[j].second) == 1)
      |                     ^~
covering.cpp:112:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  112 |                        if(abs(d[i].first - d[j].first) == 1 && abs(d[i].second - d[j].second) == 0)
      |                        ^~

• 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