Submission #1040878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040878		lovrot	Raisins (IOI09_raisins)	C++17	30 / 100	57 ms	52048 KiB

raisins

#include <cstdio>
#include <cstring> 
#include <algorithm> 

#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long ll;

const int N = 51;
const ll OO = 0x7FFFFFFFFFFFFFFF;

int n, m;
ll sum[N][N];
ll dp[N][N][N][N];

int main() { 
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) { 
		for(int j = 1; j <= m; ++j) { 
			scanf("%lld", &sum[i][j]);
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) { 
			dp[i][j][i][j] = 0;
			for(int k = i; k > 0; --k) { 
				for(int l = j - (k == i); l > 0; --l) { 
					ll &d = dp[i][j][k][l];
					d = OO;

					for(int x = k; x < i; ++x) { 
						d = min(d, dp[i][j][x + 1][l] + dp[x][j][k][l]);	
					}

					for(int y = l; y < j; ++y) { 
						d = min(d, dp[i][j][k][y + 1] + dp[i][y][k][l]);	
					}

					d += sum[i][j] - sum[i][l - 1] - sum[k - 1][l] + sum[k - 1][l - 1];
//					printf("%d %d %d %d : %d\n", i, j, k, l, dp[i][j][k][l]);
				}
			}
		}
	}

	printf("%lld\n", dp[n][m][1][1]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 100