Submission #1221569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221569		veham	T-Covering (eJOI19_covering)	C++20	5 / 100	111 ms	8208 KiB

covering

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const vi X8 = {1,1,1,0-1,-1,-1,0};
const vi Y8 = {-1,0,1,1,1,0-1,-1};
const vi X4 = {2,0,-2,0};
const vi Y4 = {0,2,0,-2};

int Calc(int m, int n, vvi &B, int k, vi &R, vi &C){
    vvi P(m,vi(n,-1));
    for(int i = 0;i < k;i++) P[R[i]][C[i]] = i;
    vi vis(k,0);
    ll ans = 0;
    for(int i = 0;i < k;i++){
        ans += B[R[i]][C[i]];
        if(!(R[i] % (m-1))){
            if(!(C[i] % (n-1))){
                return -1;
            }
            ans += B[R[i]][C[i]-1] + B[R[i]][C[i]+1] + B[R[i] + (R[i] ? -1 : 1)][C[i]];
        }
        else{
            if(!(C[i] % (n-1))) ans += B[R[i]-1][C[i]] + B[R[i]+1][C[i]] + B[R[i]][C[i] + (C[i] ? -1 : 1)];
            else{
                ans += B[R[i]][C[i]-1] + B[R[i]][C[i]+1] + B[R[i] - 1][C[i]] + B[R[i] + 1][C[i]];
                ans -= min({B[R[i]][C[i]-1],B[R[i]][C[i]+1],B[R[i] - 1][C[i]],B[R[i] + 1][C[i]]});
            }
        }
    }
    return ans;
}

int main(){
    int n,m;
    cin >> m >> n;
    vvi B(m,vi(n));
    for(int i = 0;i < m;i++) for(int j = 0;j < n;j++) cin >> B[i][j];
    int k;
    cin >> k;
    vi R(k),C(k);
    for(int i = 0;i < k;i++) cin >> R[i] >> C[i];

    cout << Calc(m,n,B,k,R,C);
    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