Submission #484447

#TimeUsernameProblemLanguageResultExecution timeMemory
484447PoPularPlusPlusRaisins (IOI09_raisins)C++17
100 / 100
185 ms26828 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pb(e) push_back(e) #define sv(a) sort(a.begin(),a.end()) #define sa(a,n) sort(a,a+n) #define mp(a,b) make_pair(a,b) #define vf first #define vs second #define ar array #define all(x) x.begin(),x.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const double PI=3.14159265358979323846264338327950288419716939937510582097494459230; bool remender(ll a , ll b){return a%b;} const int N = 51; int dp[N][N][N][N]; int p[N][N]; int cal(int x1 , int y1 , int x2 , int y2){ return p[x2][y2] - (x1 > 0 ? p[x1-1][y2] : 0) - (y1 > 0 ? p[x2][y1-1] : 0) + (x1 > 0 && y1 >0 ? p[x1-1][y1-1] : 0); } int rec(int x, int y , int x1 , int y1){ if(x == x1 && y == y1)return 0; if(dp[x][y][x1][y1] != -1)return dp[x][y][x1][y1]; int res = INT_MAX; for(int i = x; i < x1; i++){ res = min(res , rec(x,y,i,y1) + rec(i + 1 , y , x1 , y1)); } for(int j = y; j < y1; j++){ res = min(res , rec(x,y,x1,j) + rec(x,j + 1 , x1 , y1)); } return dp[x][y][x1][y1] = res + cal(x,y,x1,y1); } void solve(){ int n , m; cin >> n >> m; int arr[n][m]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> arr[i][j]; } } for(int i = 0; i < n; i++){ p[i][0] = arr[i][0]; for(int j = 1; j < m; j++)p[i][j] = p[i][j-1] + arr[i][j]; } for(int j = 0; j < m; j++){ for(int i = 1; i < n; i++){ p[i][j] += p[i-1][j]; } } memset(dp,-1,sizeof dp); cout << rec(0,0,n-1,m-1) << '\n'; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //int t;cin >> t;while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...