Submission #637589

#	Time	Username	Problem	Language	Result	Execution time	Memory
637589		ksu2009en	T-Covering (eJOI19_covering)	C++14	5 / 100	187 ms	11988 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;
    
    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;
    }
    
    return 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