Submission #311839

# Submission time Handle Problem Language Result Execution time Memory
311839 2020-10-11T23:01:29 Z ShiftyBlock Raisins (IOI09_raisins) C++11
25 / 100
5000 ms 512 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) 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

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 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 44 ms 376 KB Output is correct
6 Execution timed out 5009 ms 256 KB Time limit exceeded
7 Execution timed out 5011 ms 384 KB Time limit exceeded
8 Execution timed out 5031 ms 256 KB Time limit exceeded
9 Execution timed out 5062 ms 384 KB Time limit exceeded
10 Execution timed out 5036 ms 288 KB Time limit exceeded
11 Execution timed out 5075 ms 384 KB Time limit exceeded
12 Execution timed out 5068 ms 384 KB Time limit exceeded
13 Execution timed out 5078 ms 384 KB Time limit exceeded
14 Execution timed out 5070 ms 256 KB Time limit exceeded
15 Execution timed out 5067 ms 384 KB Time limit exceeded
16 Execution timed out 5065 ms 256 KB Time limit exceeded
17 Execution timed out 5082 ms 256 KB Time limit exceeded
18 Execution timed out 5061 ms 384 KB Time limit exceeded
19 Execution timed out 5056 ms 384 KB Time limit exceeded
20 Execution timed out 5072 ms 384 KB Time limit exceeded