Submission #1088653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088653		StefanSebez	Raisins (IOI09_raisins)	C++14	100 / 100	135 ms	25944 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int inf=1e9;
int dp[51][51][51][51];
int main(){
    int n,m;scanf("%i%i",&n,&m);
    int a[n+10][m+10],pref[n+10][m+10];memset(pref,0,sizeof(pref));
    for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%i",&a[i][j]);
			pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
		}
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) for(int l=1;l<=m;l++) dp[i][j][k][l]=inf;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j][i][j]=0;
    for(int d1=1;d1<=n;d1++){
		for(int d2=1;d2<=m;d2++){
			for(int k=d1;k<=n;k++){
				for(int l=d2;l<=m;l++){
					int i=k-d1+1,j=l-d2+1;
					int sum=pref[k][l]-pref[i-1][l]-pref[k][j-1]+pref[i-1][j-1];
					for(int ind=i+1;ind<=k;ind++){
						dp[i][j][k][l]=min(dp[i][j][k][l],sum+dp[i][j][ind-1][l]+dp[ind][j][k][l]);
					}
					for(int ind=j+1;ind<=l;ind++){
						dp[i][j][k][l]=min(dp[i][j][k][l],sum+dp[i][j][k][ind-1]+dp[i][ind][k][l]);
					}
					//printf("%i %i %i %i: %i\n",i,j,k,l,dp[i][j][k][l]);
				}
			}
		}
    }
    printf("%i\n",dp[1][1][n][m]);
    return 0;
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:11:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     int n,m;scanf("%i%i",&n,&m);
      |             ~~~~~^~~~~~~~~~~~~~
raisins.cpp:15:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |    scanf("%i",&a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100