Submission #1105779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105779		Faggi	Raisins (IOI09_raisins)	C++11	15 / 100	150 ms	131072 KiB

raisins

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll INF = LLONG_MAX;
ll calc(vector<vector<ll>>mat)
{
    ll n=mat.size(),m=mat[0].size(), res=0,j,i,tot=0,I,D,dif,miDIFi,mii,mij,miDIFj;
    vector<vector<ll>>iz,der;
    ///CASOS BASE
    if(n==1&&m==2)
    {
        res=mat[0][0]+mat[0][1];
        return res;
    }
    else if(n==2&&m==1)
    {
        res=mat[0][0]+mat[1][0];
        return res;
    }
    else if(n==1&&m==3)
    {
        res=mat[0][0]+mat[0][1]+mat[0][2];
        res+=min(mat[0][0],mat[0][2])+mat[0][1];
        return res;
    }
    else if(n==3&&m==1)
    {
        res=mat[0][0]+mat[1][0]+mat[2][0];
        res+=min(mat[0][0],mat[2][0])+mat[1][0];
        return res;
    }

    ///ARREGLOS DE CALCULO
    vector<ll>filas(n),columnas(m);
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            res+=mat[i][j];
            tot+=mat[i][j];
            filas[i]+=mat[i][j];
            columnas[j]+=mat[i][j];
        }
    }
    ///CORTES VERTICALES
    I=0; D=tot;
    miDIFj=INF;
    mij=1;
    for(i=0; i<m; i++)
    {
        I+=columnas[i];
        D-=columnas[i];
        dif=abs(I-D);
        if(miDIFj>dif)
        {
            miDIFj=dif;
            mij=i;
        }
    }
    ///CORTES HORIZONTALES
    I=0; D=tot;
    miDIFi=INF;
    mii=1;
    for(i=0; i<n; i++)
    {
        I+=filas[i];
        D-=filas[i];
        dif=abs(I-D);
        if(miDIFi>dif)
        {
            miDIFi=dif;
            mii=i;
        }
    }
    ///ELEGIR CORTE
    if(miDIFi>miDIFj)
    {
        iz.resize(n,vector<ll>(mij+1));
        der.resize(n,vector<ll>(m-(mij+1)));
        for(i=0; i<n; i++)
        {
            for(j=0; j<=mij; j++)
            {
                iz[i][j]=mat[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=mij+1; j<m; j++)
            {
                der[i][(j-mij)-1]=mat[i][j];
            }
        }
        res+=calc(iz)+calc(der);
    }
    else
    {
        iz.resize(mii+1,vector<ll>(m));
        der.resize((n-(mii+1)),vector<ll>(m));
        for(i=0; i<=mii; i++)
        {
            for(j=0; j<m; j++)
            {
                iz[i][j]=mat[i][j];
            }
        }
        for(i=mii+1; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                der[(i-(mii+1))][j]=mat[i][j];
            }
        }
        res+=calc(iz)+calc(der);
    }
    return res;
}
int main()
{
    ll n, m, i, j;
    cin >> n >> m;
    vector<vector<ll>>mat(n,vector<ll>(m));
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cin >> mat[i][j];
        }
    }
    cout << calc(mat);
    return 0;
}

• Subtask 1: 15 / 100