Submission #5365

#	Time	Username	Problem	Language	Result	Execution time	Memory
5365		model_code	Orchard (NOI14_orchard)	C++98	25 / 25	540 ms	17400 KiB

orchard

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
int N, M;
 
namespace single_row {
    const int M_ = 1000005;
    const int LEAF = 1048576;
    int A[M_], S[M_];
    int T[M_];
 
    ll solve(int h = 1) {
        for(int i = 1; i <= M; i++) S[i] = S[i-1] + A[i];
        T[M+1] = (int)1e9;
        for(int j = M; j > 0; j--) T[j] = min(T[j+1], h*j - 2*S[j]);
 
        ll ret = N*M;
        for(int i = 1; i <= M; i++) {
            ret = min(ret, (ll)S[M] - h*(i-1) + 2*S[i-1] + T[i]);
        }
 
        return ret;
    }
};
 
namespace double_rows {
    const int M_ = 100005;
    int A[2][M_], S[M_], T[M_];
 
    ll solve() {
        ll ret = N*M;
 
        for(int i = 0; i < 2; i++) for(int j = 1; j <= M; j++) scanf("%d", &A[i][j]);
        for(int k = 0; k < 2; k++) {
            int cnt = 0;
            for(int i = 1; i <= M; i++) single_row::A[i] = A[k][i];
            for(int i = 1; i <= M; i++) cnt += A[!k][i];
            ret = min(ret, single_row::solve() + cnt);
        }
 
        for(int i = 1; i <= M; i++) S[i] = S[i-1] + A[0][i] + A[1][i];
        T[M+1] = (int)1e9;
        for(int j = M; j > 0; j--) T[j] = min(T[j+1], 2*j - 2*S[j]);
 
        for(int i = 1; i <= M; i++) {
            ret = min(ret, (ll)S[M] - 2*(i-1) + 2*S[i-1] + T[i]);
        }
 
        return ret;
    }
};
 
namespace many_rows {
    int D[155][5005];
    int RS[155];
    ll solve() {
        ll ret = (ll)N*M;
        for(int i = 1; i <= N; i++) {
            RS[i] = RS[i-1];
            for(int j = 1; j <= M; j++) {
                scanf("%d", &D[i][j]);
                RS[i] += D[i][j];
                D[i][j] += D[i-1][j];
            }
        }
 
        for(int i = 1; i <= N; i++) for(int j = i; j <= N; j++) {
            for(int k = 1; k <= M; k++) single_row::A[k] = D[j][k] - D[i-1][k];
            ret = min(ret, RS[i-1] + RS[N] - RS[j] + single_row::solve(j-i+1));
        }
 
        return ret;
    }
};
 
int main() {
    ll res;
 
    scanf("%d%d", &N, &M); res = (ll)N*M;
    if(N == 1) {
        for(int i = 1; i <= M; i++) scanf("%d", single_row::A+i);
        res = single_row::solve();
    }else if(N == 2){
        res = double_rows::solve();
    }else {
        res = many_rows::solve();
    }
 
    printf("%lld\n", res);
 
    return 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