Submission #1177343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177343		ksu2009en	Orchard (NOI14_orchard)	C++20	25 / 25	202 ms	23900 KiB

orchard

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

int main(){
    ll n, m;
    cin >> n >> m;
    
    vector<vector<ll>> a(n, vector<ll> (m));
    ll tot = 0;
    
    for(auto &i: a)
        for(auto &j: i){
            cin >> j;
            tot += j;
        }
    
    ll ans = n * m;
    
    vector<ll> pref0(m), pref1(m);
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            pref0[j] = pref1[j] = 0;
        
        for(int j = i; j < n; j++){
            ll cur0 = 0, cur1 = 0;
            for(int p = 0; p < m; p++){
                cur0 += (1 - a[j][p]);
                cur1 += a[j][p];
                
                pref0[p] += cur0;
                pref1[p] += cur1;
            }
            
            ll mn = 0;
            
            for(int p = 0; p < m; p++){
                ans = min(ans, pref0[p] - pref1[p] + mn);

                mn = min(mn, pref1[p] - pref0[p]);
            }
        }
    }
    
    cout << ans + tot << endl;
    
    return 0;
}
/*
 5 7
 0 0 1 0 0 1 0
 0 1 1 1 1 1 0
 0 1 1 0 0 1 0
 0 1 1 1 1 1 0
 0 0 1 0 0 1 0
 
 */

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