Submission #526097

#	Time	Username	Problem	Language	Result	Execution time	Memory
526097		Deepesson	Raisins (IOI09_raisins)	C++17	100 / 100	613 ms	27528 KiB

raisins

#include <bits/stdc++.h>
#define MAX 51
int tab[MAX][MAX];
int N,M;
int sumed[MAX][MAX];
int t(int x,int y) {
    if(x<0||y<0)return 0;
    return sumed[x][y];
}
int subrec(int x1,int y1,int x2,int y2) {
    return t(x2,y2)-t(x2,y1-1)-t(x1-1,y2)+t(x1-1,y1-1);
}
int resp[MAX][MAX][MAX][MAX];
bool exist[MAX][MAX][MAX][MAX];
int dp(int x1,int y1,int x2,int y2) {
    if(x1==x2&&y1==y2)return 0;
    if(exist[x1][y1][x2][y2])return resp[x1][y1][x2][y2];
    exist[x1][y1][x2][y2]=true;
    int custo = subrec(x1,y1,x2,y2);
    int best = 1e9;
    for(int i = x1;i!=x2;++i) {
        best = std::min(best,(int)(dp(x1,y1,i,y2)+dp(i+1,y1,x2,y2)));
    }
    for(int i = y1;i!=y2;++i) {
        best = std::min(best,(int)(dp(x1,y1,x2,i)+dp(x1,i+1,x2,y2)));
    }
    return resp[x1][y1][x2][y2]=best+custo;
}
int main()
{
    std::cin >> N >> M;
    for(int i = 0; i != N;++i) {
        for(int j = 0; j != M;++j) {
            std::cin>> tab[i][j];
        }
    }
    for(int i = 0; i != N;++i) {
        int val = 0;
        for(int j = 0; j != M;++j) {
            val += tab[i][j];
            sumed[i][j]=val;
            if(i)sumed[i][j]+=sumed[i-1][j];
        }
    }
    std::cout << dp(0,0,N-1,M-1) << std::endl;
}

• Subtask 1: 100 / 100