# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
593212 | Bench0310 | Raisins (IOI09_raisins) | C++17 | 155 ms | 24816 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50;
int a[N][N];
int sum[N][N];
int dp[N][N][N][N];
void chmin(int &x,int y){x=min(x,y);}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin >> a[i][j];
sum[i][j]=(i>0?sum[i-1][j]:0)+(j>0?sum[i][j-1]:0)-((i>0&&j>0)?sum[i-1][j-1]:0)+a[i][j];
}
}
memset(dp,127,sizeof(dp));
for(int sr=1;sr<=n;sr++)
{
for(int sc=1;sc<=m;sc++)
{
for(int li=0;li+sr-1<n;li++)
{
int ri=li+sr-1;
for(int lj=0;lj+sc-1<m;lj++)
{
int rj=lj+sc-1;
int s=(sum[ri][rj]-(li>0?sum[li-1][rj]:0)-(lj>0?sum[ri][lj-1]:0)+((li>0&&lj>0)?sum[li-1][lj-1]:0));
int &d=dp[li][ri][lj][rj];
if(sr==1&&sc==1) d=0;
//horizontal
for(int i=li;i<ri;i++) chmin(d,dp[li][i][lj][rj]+dp[i+1][ri][lj][rj]+s);
//vertical
for(int j=lj;j<rj;j++) chmin(d,dp[li][ri][lj][j]+dp[li][ri][j+1][rj]+s);
}
}
}
}
cout << dp[0][n-1][0][m-1] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |