Submission #348320

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348320	2021-01-14T15:21:22 Z	Mefarnis	Raisins (IOI09_raisins)	C++14	100 / 100	2070 ms	53516 KB

raisins

#include <bits/stdc++.h>
#define maxn 51
using namespace std;
typedef long long LL;

int n,m;
int ar[maxn][maxn];
int sum[maxn][maxn];
LL dp[maxn][maxn][maxn][maxn];

int query(int r1 , int c1 , int r2 , int c2) {
	return sum[r2][c2] + sum[r1-1][c1-1] - sum[r2][c1-1] - sum[r1-1][c2];
}

LL f(int r1 , int c1 , int r2 , int c2) {
	if(r1 == r2 && c1 == c2)
		return 0;
	if(dp[r1][c1][r2][c2] != -1)
		return dp[r1][c1][r2][c2];
	dp[r1][c1][r2][c2] = LLONG_MAX;
	int add = query(r1,c1,r2,c2);
	for( int c = c1 ; c < c2 ; c++ ) {
		LL cost = f(r1,c1,r2,c) + f(r1,c+1,r2,c2) + add;
		dp[r1][c1][r2][c2] = min(dp[r1][c1][r2][c2],cost);
	}
	for( int r = r1 ; r < r2 ; r++ ) {
		LL cost = f(r1,c1,r,c2) + f(r+1,c1,r2,c2) + add;
		dp[r1][c1][r2][c2] = min(dp[r1][c1][r2][c2],cost);
	}
	return dp[r1][c1][r2][c2];
}

int main() {
	scanf("%d%d",&n,&m);
	for( int i = 1 ; i <= n ; i++ )
		for( int j = 1 ; j <= m ; j++ ) {
			scanf("%d",&ar[i][j]);
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + ar[i][j];
		}
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",f(1,1,n,m));
	return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	53228 KB	Output is correct
2	Correct	29 ms	53228 KB	Output is correct
3	Correct	29 ms	53228 KB	Output is correct
4	Correct	29 ms	53228 KB	Output is correct
5	Correct	30 ms	53228 KB	Output is correct
6	Correct	29 ms	53228 KB	Output is correct
7	Correct	30 ms	53228 KB	Output is correct
8	Correct	39 ms	53228 KB	Output is correct
9	Correct	50 ms	53356 KB	Output is correct
10	Correct	60 ms	53228 KB	Output is correct
11	Correct	53 ms	53228 KB	Output is correct
12	Correct	137 ms	53356 KB	Output is correct
13	Correct	220 ms	53356 KB	Output is correct
14	Correct	72 ms	53228 KB	Output is correct
15	Correct	279 ms	53356 KB	Output is correct
16	Correct	50 ms	53356 KB	Output is correct
17	Correct	114 ms	53356 KB	Output is correct
18	Correct	715 ms	53356 KB	Output is correct
19	Correct	1467 ms	53516 KB	Output is correct
20	Correct	2070 ms	53484 KB	Output is correct