Submission #638502

#	Time	Username	Problem	Language	Result	Execution time	Memory
638502		ShirleyM	T-Covering (eJOI19_covering)	C++14	5 / 100	61 ms	12000 KiB

covering

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
#define fast {ios_base::sync_with_stdio(false); cin.tie(0);}
const int inf = 1e18;
const int INF = 1e9;
const int mod = 1e9+7;

int n,m,k;
vvi g;
vii special;

bool in_limits(int i, int j){
    return (i>=0 && i<n && j>=0 && j<m);
}

int best(int i, int j){
    /*int op1=g[i][j], op2=0, op3=0, op4=0;
    op2 = op3 = op4 = op1;
    vii d = {{-1,0}, {0,-1}, {0,1}, {1,0}};
    for(auto it : d){
        int di = it.x, dj = it.y;
        int ni = i+di, nj = j+dj;
        bool bad = 0;
        if(!in_limits(ni,nj)) bad=1;
        if(di==-1){
            if(bad) op1 = op2= op4 = -inf;
            else {
                op1 += g[ni][nj];
                op2 += g[ni][nj];
                op4 += g[ni][nj];
            }
        }
        if(di==1){
            if(bad) op2 = op3= op4 = -inf;
            else {
                op2 += g[ni][nj];
                op3 += g[ni][nj];
                op4 += g[ni][nj];
            }
        }
        if(dj==-1){
            if(bad) op1 = op3= op4 = -inf;
            else {
                op1 += g[ni][nj];
                op3 += g[ni][nj];
                op4 += g[ni][nj];
            }
        }
        if(dj==1) {
            if (bad) op1 = op2 = op3 = -inf;
            else {
                op1 += g[ni][nj];
                op2 += g[ni][nj];
                op3 += g[ni][nj];
            }
        }
    }
    int ans = max({op1,op2,op3,op4});
    return ans;*/

    int ans = g[i][j];
    vi a;
    vii d = {{-1,0}, {0,-1}, {0,1}, {1,0}};
    for(auto it : d){
        int di = it.x, dj = it.y;
        int ni = i+di, nj = j+dj;
        if(!in_limits(ni,nj)) continue;
        a.pb(g[ni][nj]);
    }
    if(a.size() <=2) return -1;
    sort(all(a), greater<int>());
    loop(ind,0,3) ans += a[ind];
    return ans;
}

int32_t main() {
    fast;
    cin >> n >> m;
    g.resize(n, vi(m));
    loop(i,0,n) loop(j,0,m) cin >> g[i][j];
    cin >> k; special.resize(k);
    loop(i,0,k) cin >> special[i].x >> special[i].y;
    int ans = 0;
    loop(i,0,k){
        int cur_ans = best(special[i].x, special[i].y);
        if(cur_ans < 0){
            cout << "No";
            return 0;
        }
        ans += cur_ans;
    }
    cout << ans;
    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