Submission #311839

#	Time	Username	Problem	Language	Result	Execution time	Memory
311839		ShiftyBlock	Raisins (IOI09_raisins)	C++11	25 / 100	5082 ms	512 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define long long long
#define v vector
#define rep(i,a,b) for(int i=a; i<b; i++)
void setIO(string name, int submit) {
    if (submit) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
const int MAXN=52;
int arr[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int N, M;
int recurse(int ix, int iy, int jx, int jy){
	if(jx-ix==0 && jy-iy==0) return 0;
	int best=1<<30;
	for(int row= iy+1; row<=jy; row++){
		best= min(best, recurse(ix, iy, jx, row-1)+ recurse(ix, row, jx, jy));
	}
	for(int col= ix+1; col<=jx; col++){
		best= min(best, recurse(col, iy, jx, jy)+ recurse(ix, iy, col-1, jy));
	}
	int base=arr[jx][jy]-arr[ix-1][jy]-arr[jx][iy-1]+arr[ix-1][iy-1];
	return base+best;
}
int main() {
    setIO("", 0);
    cin >>N>>M;
    rep(i,1,N+1){
    	rep(j,1,M+1){
    		cin>> arr[i][j];
    		arr[i][j]+=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
    	}
    }
    cout << recurse(1,1,N,M)<< endl;
    
    return 0;
}

Compilation message (stderr)

raisins.cpp: In function 'void setIO(std::string, int)':
raisins.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raisins.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 100