Submission #277701

#	Time	Username	Problem	Language	Result	Execution time	Memory
277701		barsbold	Raisins (IOI09_raisins)	C++14	100 / 100	1272 ms	27136 KiB

raisins

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pb push_back
#define ll long long
using namespace std;
int a[2001][2001];  
int dp[51][51][51][51];
int solve(int l , int r , int L , int R){
    if(l == r && L == R){
        return 0;
    }
    if(l >r || L > R){
        return 0;
    }
    if(dp[l][r][L][R] != -1) return dp[l][r][L][R];
    int sum =0;
    for(int i =l ; i<=r; i++){
        for(int j = L; j<=R; j++){
            sum+=a[i][j];
        }
    }
    int res = 1e9;
   for(int i = l ; i<=r-1; i++){
       res = min(res , solve(l , i , L , R) + solve(i + 1 , r , L ,R) + sum);
   } 
   for(int i = L; i<=R-1; i++){
       res = min(res , solve(l , r , L , i) + solve(l, r , i + 1 , R) + sum);
   }
    return dp[l][r][L][R] = res;
}
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    int n , m;
    cin >> n >> m;
    memset(dp , -1 , sizeof(dp));
    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            cin >> a[i][j];
        }
    }
    cout << solve(1 , n , 1 , m) << endl;
    return 0;


}

• Subtask 1: 100 / 100