Submission #295991

#	Time	Username	Problem	Language	Result	Execution time	Memory
295991		Hemimor	Raisins (IOI09_raisins)	C++14	100 / 100	1002 ms	14104 KiB

raisins

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=52;
int n,m,dp[M][M][M][M];
vvi a;

int f(int x,int X,int y,int Y){
	if(x+1==X&&y+1==Y) return 0;
	if(dp[x][X][y][Y]) return dp[x][X][y][Y];
	int mn=inf;
	for(int i=x+1;i<X;i++) mn=min(mn,f(x,i,y,Y)+f(i,X,y,Y));
	for(int i=y+1;i<Y;i++) mn=min(mn,f(x,X,y,i)+f(x,X,i,Y));
	return dp[x][X][y][Y]=mn+a[X][Y]-a[x][Y]-a[X][y]+a[x][y];
}

int main(){
	scanf("%d%d",&n,&m);
	a=vvi(n+1,vi(m+1));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	printf("%d\n",f(0,n,0,m));
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
raisins.cpp:54:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
      |                                              ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100