제출 #660280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660280		ivopav	건포도 (IOI09_raisins)	C++14	100 / 100	914 ms	29388 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

int sum(const vector<vector<int>>& mat2,int x1,int y1,int x2,int y2){
    if (x1==0 && y1==0){
        return mat2[y2][x2];
    }
    else if(x1==0){
        return mat2[y2][x2]-mat2[y1-1][x2];
    }
    else if(y1==0){
        return mat2[y2][x2]-mat2[y2][x1-1];
    }
    else{
        return mat2[y2][x2]-mat2[y1-1][x2]-mat2[y2][x1-1]+mat2[y1-1][x1-1];
    }
}

int rek(const vector<vector<int>>& mat,const vector<vector<int>>& mat2,vector<vector<vector<vector<int>>>>& mem,int x1,int y1,int x2,int y2){
    if (x1==x2 && y1==y2){
        return 0;
    }
    if (mem[x1][y1][x2][y2]!=-1){
        return mem[x1][y1][x2][y2];
    }
    int najm=numeric_limits<int>::max(); 
    for (int i=x1;i<x2;i++){
        int pom=rek(mat,mat2,mem,x1,y1,i,y2);
        int pom2=rek(mat,mat2,mem,i+1,y1,x2,y2);
        najm=min(najm,pom+pom2);
    }
    for (int i=y1;i<y2;i++){
        int pom=rek(mat,mat2,mem,x1,y1,x2,i);
        int pom2=rek(mat,mat2,mem,x1,i+1,x2,y2);
        najm=min(najm,pom+pom2);
    }
    mem[x1][y1][x2][y2]=najm+sum(mat2,x1,y1,x2,y2);
    return najm+sum(mat2,x1,y1,x2,y2);
}

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<vector<int>> mat={};
    for (int i=0;i<n;i++){  
        mat.push_back({});
        for (int j=0;j<m;j++){
            int unos;
            cin >> unos;
            mat[i].push_back(unos);
        }
    }
    vector<vector<int>> mat2={};
    for (int i=0;i<n;i++){
        mat2.push_back({});
        for (int j=0;j<m;j++){
            if (i==0 && j==0){
                mat2[i].push_back(mat[i][j]);
            }
            else if(i==0){
                mat2[i].push_back(mat[i][j]+mat2[i][j-1]);
            }
            else if(j==0){
                mat2[i].push_back(mat[i][j]+mat2[i-1][j]);
            }
            else{
                mat2[i].push_back(mat[i][j]+mat2[i][j-1]+mat2[i-1][j]-mat2[i-1][j-1]);
            }
            
            
        }
    }
    vector<vector<vector<vector<int>>>> mem=vector<vector<vector<vector<int>>>>(m,vector<vector<vector<int>>>(n,vector<vector<int>>(m,vector<int>(n,-1))));
   // cout << sum(mat2,0,1,2,3) << "\n";
    cout << rek(mat,mat2,mem,0,0,m-1,n-1) << "\n";
}  

• Subtask 1: 100 / 100