Submission #242321

#	Time	Username	Problem	Language	Result	Execution time	Memory
242321		valerikk	T-Covering (eJOI19_covering)	C++17	0 / 100	6 ms	640 KiB

covering

#include<bits/stdc++.h>
using namespace std;

//#define int long long 

const vector<vector<pair<int, int>>> T = {{{0, 0}, {0, -1}, {0, 1}, {1, 0}}, {{0, 0}, {0, -1}, {0, 1}, {-1, 0}}, {{0, 0}, {-1, 0}, {1, 0}, {0, 1}}, {{0, 0}, {-1, 0}, {1, 0}, {0, -1}}};
const int INF = 1e9 + 228;

int n, m;
vector<vector<int>> a;

inline bool check(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

inline void upd(int &x, int y) {
    if(y > x)
        x = y;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    a.assign(n, vector<int>(m));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> a[i][j];
        }
    }
    int k;
    cin >> k;
    vector<pair<int, int>> t(k);
    for(int i = 0; i < k; ++i){
        cin >> t[i].first >> t[i].second;
    }
    sort(t.begin(), t.end());
    vector<vector<int>> dp(k, vector<int>(4, -INF));
    for(int i = 0; i < 4; ++i){
        bool ok = 1;
        int sum = 0;
        for(auto pp : T[i]){
            ok &= check(t[0].first + pp.first, t[0].second + pp.second);
            if(ok){
                sum += a[t[0].first + pp.first][t[0].second + pp.second];
            } else{
                break;
            }
        }
        if(ok){
            dp[0][i] = sum;
        }
    }
    for(int i = 1; i < k; ++i) {
        for(int j = 0; j < 4; ++j){
            bool ok = 1;
            int sum = 0;
            vector<pair<int, int>> v1;
            for(auto pp : T[i]){
                ok &= check(t[i].first + pp.first, t[i].second + pp.second);
                v1.emplace_back(t[i].first + pp.first, t[i].second + pp.second);
                if(ok){
                    sum += a[t[i].first + pp.first][t[i].second + pp.second];
                } else{
                    break;
                }
            }
            if(ok){
                sort(v1.begin(), v1.end());
                for(int jj = 0; jj < 4; ++jj){
                    if(dp[i - 1][jj] == -INF)
                        continue;
                    vector<pair<int, int>> v2;
                    for(auto pp : T[jj]){
                        v2.emplace_back(t[i - 1].first + pp.first, t[i - 1].second + pp.second);
                    }
                    sort(v2.begin(), v2.end());
                    bool good = 1;
                    for(auto pp : v1){
                        auto it = lower_bound(v2.begin(), v2.end(), pp);
                        good &= it == v2.end() || *it != pp;
                        if(!good){
                            break;
                        }
                    }
                    if(good){
                        upd(dp[i][j], dp[i - 1][jj] + sum);
                    }
                }
            }
        }
    }
    int ans = -INF;
    for(int i = 0; i < 4; i++){
        upd(ans, dp[k - 1][i]);
    }
    if(ans == -INF){
        cout << "No";
    } else{
        cout << ans;
    }
    return 0;
}

• Subtask 1: 0 / 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