Submission #374587

#	Time	Username	Problem	Language	Result	Execution time	Memory
374587		Karliver	Raisins (IOI09_raisins)	C++14	100 / 100	1297 ms	26992 KiB

raisins

#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(3)<<(x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 51;
const double eps = 1e-3;

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


ll power(ll a, ll b){
    if(!b)
        return 1;
    ll c=power(a,b/2);
    c=(1LL*c*c);
    if(b%2)
        c=(1LL*c*a);
    return c;
}


int mul(int a, int b) {
    return a * 1ll * b % mod;
}
int add(int a, int b) {
    int s = (a+b);
    if (s>=mod) s-=mod;
    return s;
}



struct RMQ {
    vector<vector<int>>st;
    RMQ(vector<int> &a) {
        int n = a.size();
        int k = ceil(log2(n));
        st.clear();
        st = vector<vector<int>>(n, vector<int>(k + 1, INF));
        for(int i = 0;i < n;++i) {
            st[i][0] = a[i];
        }
        for(int j = 1;j <= k;++j) {
            for(int i = 0;i + (1 << j) <= n;++i) {
                st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }

    }
    int rng_q(int l, int r) {
        //if(l > r)return -1;
        int j = log2(r - l + 1);
        int ans = min(st[l][j], st[r - (1 << j) + 1][j]);
        return ans;
    }

};

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;


template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(n < 0 || r < 0 || n < r) return 0;
		return fact[n]  * factinv[r] *  factinv[n - r];
	}
	T factorial(int x) {
        if(x < 0)return 0;
        return fact[x];
	}
};


void done() {

    // -1
    // 1 -2
    // -2

}

void solve()
{


    // 4 5 2 3 1
    // 1 -3 1 -2
    // 4 6 3 1 5 2
    // 2 -3 -2 4 -3

    int n, m;
    cin >> n >> m;

    int DP[N][N][N][N];
    forn(i, N) forn(j, N) forn(l, N) forn(K, N) DP[i][j][l][K] = -1;
    int pr[N][N];
    forn(i, N)forn(j, N)pr[i][j] = 0;

    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            cin >> a[i][j];
            pr[i][j] = pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1] + a[i][j];
        }
    }

    function<int(int, int, int, int)> dfs = [&](int x1, int y1, int x2, int y2) {
        if (DP[x1][y1][x2][y2] > -1)
            return DP[x1][y1][x2][y2];
        if (x1 == x2 && y1 == y2)
        {
            DP[x1][y1][x2][y2] = 0;
            return 0;
        }
        int res = INT_MAX;
        int n1 = 0;
        int n2 = 0;
        for (int i = x1; i < x2; i++)
        {
            n1 = dfs(x1,y1,i,y2);
            n2 = dfs(i + 1,y1,x2,y2);
            if (n1 + n2 < res)
                res = n1 + n2;
        }
        for (int i = y1; i < y2; i++)
        {
            n1 = dfs(x1,y1,x2,i);
            n2 = dfs(x1,i + 1,x2,y2);
            if (n1 + n2 < res)
                res = n1 + n2;
        }
        res += pr[x2][y2] - pr[x1 - 1][y2] - pr[x2][y1 - 1] + pr[x1 - 1][y1 - 1];
        DP[x1][y1][x2][y2] = res;
        return res;

    };

    cout << dfs(1, 1, n, m) << '\n';


}


void emer() {





}

void another() {

    // 10011
    //
    int n, q;
    cin>> n >> q;
    vector<int> c(n);
    for(int i = 0;i < n;++i) {
        cin >> c[i];
    }

    vector<vector<pair<int, pairs>>> qur(n);
    for(int i = 0;i < q;++i) {
        int l, r;
        cin>> l >> r;
        --l;
        --r;
        qur[r].push_back({l, {i, 1}});
        if(l) {
            qur[l - 1].push_back({l, {i, -1}});
        }
    }
    vector<int> f(n);

    auto inc = [&](int x) {
        for(; x < n;x = (x | (x + 1))) f[x]++;
    };
    auto get = [&](int  x) {
        int ans =0;
        for(; x >= 0;x = (x & (x + 1)) - 1)
            ans += f[x];
        return ans;
    };

    vector<int> ret(q);
    map<int, int> last;
    vector<int> pev(n, -1);

    for(int i = 0;i < n;++i) {
        if(last.count(c[i])) {
            pev[i] = last[c[i]];
        }
        last[c[i]] = i;
        inc(pev[i] + 1);
        for(auto c : qur[i]) {
            ret[c.second.first] += get(c.first) * c.second.second;
            //cout << ret[c.second.first] << '\n';

        }
    }

    forn(i, q) cout << ret[i] << '\n';

    // 1 6 4 1 2 2 8
    // (1, 3) (2, 5)
    // 3 0 0 0 0 0 0


}
void test_case() {
    int t;
    cin >> t;
    while(t--)solve();
}
int main() {



    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();





}

• Subtask 1: 100 / 100