Submission #197523

#	Time	Username	Problem	Language	Result	Execution time	Memory
197523		handlename	Orchard (NOI14_orchard)	C++17	25 / 25	178 ms	18040 KiB

orchard

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int arr[n+1][m+1],total=0;
    memset(arr,0,sizeof(arr));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>arr[i][j];
            if (arr[i][j]==0) arr[i][j]=-1;
            else total++;
        }
    }
    int pre[n+1][m+1];
    memset(pre,0,sizeof(pre));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            pre[i][j]=pre[i-1][j]+arr[i][j];
        }
    }
    int maxi=0;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            int currentsum=0;
            for (int k=1;k<=m;k++){
                currentsum+=pre[j][k]-pre[i-1][k];
                maxi=max(maxi,currentsum);
                if (currentsum<0) currentsum=0;
            }
        }
    }
    cout<<total-maxi;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5