Submission #1221714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221714		mayac	T-Covering (eJOI19_covering)	C++20	0 / 100	1 ms	328 KiB

covering

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll=long long;
const int inf=-(1e9);
int main(){
    int n,m,ans=0,k,a,b,cur;
    cin>>n>>m;
    vector<vector<int>> v(n,vector<int>(m,-1));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
        }
    }
    cin>>k;
    bool flag=1,tmp;
    vector<int> p(k+1);
    p[0]=-10;
    for(int i=0;i<k;i++){
        cin>>a>>b;
        p[i+1]=b;
    }
    vector<int> dp(k+1,0),dp2(k+1,0);
    sort(p.begin(),p.end());
    if(n<2)flag=0;
    else{
    if(a==0){
        for(int i=0;i<k;i++){
            if(i>0&&p[i]-p[i-1]<3)flag=0;
            else{
                b=p[i];
                ans+=v[a][b]+v[a+1][b]+v[a][b-1]+v[a][b+1];
            }
        }
    }
    else if(a==n-1){
        for(int i=0;i<k;i++){
            if(i>0&&p[i]-p[i-1]<3)flag=0;
            else{
                b=p[i];
                ans+=v[a][b]+v[a-1][b]+v[a][b-1]+v[a][b+1];
            }
        }
    }else{
        
        for(int i=1;i<=k;i++){
            dp2[i]=v[a][b]+v[a+1][b]+v[a-1][b]+v[a][b+1]+dp2[i-1];
            if(p[i]-p[i-1]==0){
                flag=0;
            }
            else if(p[i]-p[i-1]==1){
                dp[i]=inf;
                b=p[i];
            }
            else if(p[i]-p[i-1]==2){
                dp2[i]=max(dp2[i],v[a][b]+v[a+1][b]+v[a-1][b]+v[a][b-1]+dp2[i-1]);
                dp[i]=max(dp[i],v[a][b]+v[a+1][b]+v[a][b+1]+v[a][b-1]+dp2[i-1]);
                dp[i]=max(dp[i],v[a][b]+v[a-1][b]+v[a][b+1]+v[a][b-1]+dp2[i-1]);
            }
            if(p[i]-p[i-1]>=3){
                dp2[i]=max(dp2[i],v[a][b]+v[a+1][b]+v[a-1][b]+v[a][b-1]+dp[i-1]);
                dp[i]=max(dp[i],v[a][b]+v[a+1][b]+v[a][b+1]+v[a][b-1]+dp[i-1]);
                dp[i]=max(dp[i],v[a][b]+v[a-1][b]+v[a][b+1]+v[a][b-1]+dp[i-1]);
            }
            dp[i]=max(dp[i],dp2[i]);
        }
    }
    }
    if(flag)cout<<dp[k]<<"\n";
    else cout<<"No\n";
}

• 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