Submission #311840

# Submission time Handle Problem Language Result Execution time Memory
311840 2020-10-11T23:10:18 Z ShiftyBlock Raisins (IOI09_raisins) C++11
0 / 100
18 ms 27008 KB
#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) {
		dp[ix][iy][jx][jy]=0;
	}
	if(dp[ix][iy][jx][jy]!=-1){
		int best=1<<30;
		for(int row= iy+1; row<=jy; row++){
			best= min(best, recurse(ix, row, jx, jy)+recurse(ix, iy, jx, row-1));
		}
		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];
		dp[ix][iy][jx][jy]= best+base;
	}
	return dp[ix][iy][jx][jy];
}

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];
    	}
    }
    rep(i,1,N+1){
    	rep(j,1,M+1){
    		rep(k,1,N+1){
    			rep(l,1,M+1){
    				dp[i][j][k][l]=-1;
    			}
    		}
    	}
    }
    cout << recurse(1,1,N,M)<< endl;
    
    return 0;
}

Compilation message

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Incorrect 1 ms 512 KB Output isn't correct
6 Incorrect 1 ms 1024 KB Output isn't correct
7 Incorrect 1 ms 1152 KB Output isn't correct
8 Incorrect 2 ms 3456 KB Output isn't correct
9 Incorrect 3 ms 4992 KB Output isn't correct
10 Incorrect 4 ms 5888 KB Output isn't correct
11 Incorrect 3 ms 4992 KB Output isn't correct
12 Incorrect 7 ms 10624 KB Output isn't correct
13 Incorrect 8 ms 13312 KB Output isn't correct
14 Incorrect 4 ms 6144 KB Output isn't correct
15 Incorrect 8 ms 14464 KB Output isn't correct
16 Incorrect 3 ms 4992 KB Output isn't correct
17 Incorrect 6 ms 9728 KB Output isn't correct
18 Incorrect 14 ms 20864 KB Output isn't correct
19 Incorrect 17 ms 25344 KB Output isn't correct
20 Incorrect 18 ms 27008 KB Output isn't correct