Submission #638555

#	Time	Username	Problem	Language	Result	Execution time	Memory
638555		ShirleyM	T-Covering (eJOI19_covering)	C++14	10 / 100	12 ms	1492 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 = 1e11;
const int INF = 1e9;
const int mod = 1e9+7;

int n,m,k;
vvi g;
vii sp;
vvi st;
vvb s;

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

int best(int i, int j){
    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;
}

int get_from_st(int i, int j, int st){
    if(st == -1) return best(i,j);
    int ans = g[i][j];
    int u = in_limits(i-1,j) ? g[i-1][j] : -inf;
    int d = in_limits(i+1,j) ? g[i+1][j] : -inf;
    int l = in_limits(i,j-1) ? g[i][j-1] : -inf;
    int ri = in_limits(i,j+1) ? g[i][j+1] : -inf;
    if(st==0) ans += u+d+l;
    if(st == 1) ans += u+d+ri;
    else if(st==2) ans += u+l+ri;
    else if(st==3) ans += d+l+ri;
    return ans;
}

void put(int i, int j, int state){
    if(st[i][j] != -1 && st[i][j] != state){
        cout << "No";
        exit(0);
    }
    st[i][j] = state;
}

int32_t main() {
    fast;
    cin >> n >> m;
    g.resize(n, vi(m));
    //st.resize(n, vi(m, -1));
    s.resize(n, vb(m, -1));
    loop(i,0,n) loop(j,0,m) cin >> g[i][j];
    cin >> k; sp.resize(k);
    loop(i,0,k){
        cin >> sp[i].x >> sp[i].y;
        s[sp[i].x][sp[i].y]=true;
    }
    sort(all(sp));
    int ans = 0;
    /*loop(i,0,k){
        int r1 = r[i], c1 = c[i];
        loop(j,i+1,k){
            int r2 = r[j], c2 = c[j];
            if(abs(r1-r2) <= 1 && abs(c1-c2) <= 1){
                if(c1==c2) {
                    if (r1 == r2 - 1) {
                        put(r1, c1, 1);
                        put(r2, c2, 3);
                    }
                    if (r2 == r1 - 1) {
                        put(r1, c1, 3);
                        put(r2, c2, 1);
                    }
                }
                else if(r1==r2){
                    if(c1 == c2-1){
                        put(r1,c1,4);
                        put(r2,c2,2);
                    }
                    if(c2 == c1-1){
                        put(r1,c1,2);
                        put(r2,c2,4);
                    }
                }
                else if(r1 < r2){
                    put(r1,c1,1);
                    put(r2,c2,3);
                }
                else if(r2 < r1){
                    put(r1,c1,3);
                    put(r2,c2,1);
                }
            }
        }
    }
    loop(i,0,k){
        ans += get_from_st(r[i], c[i]);
    }*/
    vvi dp(k+1, vi(4));
    loop(i,0,k){
        loop(j,0,4){
            if(dp[i][j] < 0){
                dp[i][j] = -1e18; continue;
            }
            dp[i][j] += get_from_st(sp[i].x, sp[i].y, j);
            if(dp[i][j] < 0) dp[i][j] = -1e18;
        }
        if(i==k-1) break;
        int cur = sp[i].y, next = sp[i+1].y;
        if(next == cur+1) dp[i+1][1] += dp[i][0];
        else if(next == cur+2){
            dp[i+1][1] +=  max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
            dp[i+1][0] += dp[i][0];
            dp[i+1][2] += dp[i][0];
            dp[i+1][3] += dp[i][0];
        }
        else {
            int mx = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3]});
            loop(st2, 0, 4) {
                dp[i + 1][st2] += mx;
            }
        }
    }
    ans = max({dp[k-1][0], dp[k-1][1], dp[k-1][2], dp[k-1][3]});
    if(ans<0) cout << "No";
    else cout << ans;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30