Submission #245303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245303	2020-07-06T02:24:39 Z	Marlov	Raisins (IOI09_raisins)	C++14	15 / 100	5000 ms	20608 KB

raisins

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define maxV 50
#define INF 10000
int N,M;
int arr[maxV][maxV];
int dp[maxV][maxV][maxV][maxV];

int psum(int a,int b,int x,int y){
	int v=0;
	for(int i=a;i<=x;i++){
		for(int j=b;j<=y;j++){
			v+=arr[i][j];
		}
	}
	return v;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>M;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			for(int a=i;a<N;a++){
				for(int b=j;b<M;b++){
					dp[i][j][a][b]=INF;
				}
			}
		}
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin>>arr[i][j];
			dp[i][j][i][j]=0;
		}
	}
	//loc size
	for(int a=0;a<N;a++){
		for(int b=0;b<M;b++){
			//starting loc x,y
			for(int x=0;x+a<N;x++){
				for(int y=0;y+b<M;y++){
					//splits
					//1D
					for(int i=1;i<=a;i++){
						dp[x][y][x+a][y+b]=min(dp[x][y][x+a][y+b],dp[x][y][x+i-1][y+b]+dp[x+i][y][x+a][y+b]+psum(x,y,x+a,y+b));
					}
					//2d
					for(int i=1;i<=b;i++){
						dp[x][y][x+a][y+b]=min(dp[x][y][x+a][y+b],dp[x][y][x+a][y+i-1]+dp[x][y+i][x+a][y+b]+psum(x,y,x+a,y+b));
					}
				}
			}

		}
	}
	cout<<dp[0][0][N-1][M-1]<<'\n';
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Incorrect	5 ms	384 KB	Output isn't correct
5	Incorrect	5 ms	512 KB	Output isn't correct
6	Incorrect	5 ms	896 KB	Output isn't correct
7	Incorrect	6 ms	1024 KB	Output isn't correct
8	Incorrect	43 ms	2688 KB	Output isn't correct
9	Incorrect	88 ms	3832 KB	Output isn't correct
10	Incorrect	148 ms	4352 KB	Output isn't correct
11	Incorrect	124 ms	3840 KB	Output isn't correct
12	Incorrect	673 ms	7520 KB	Output isn't correct
13	Incorrect	1372 ms	9464 KB	Output isn't correct
14	Incorrect	232 ms	4856 KB	Output isn't correct
15	Incorrect	1837 ms	10368 KB	Output isn't correct
16	Incorrect	70 ms	3584 KB	Output isn't correct
17	Incorrect	485 ms	7168 KB	Output isn't correct
18	Execution timed out	5060 ms	15744 KB	Time limit exceeded
19	Execution timed out	5075 ms	19200 KB	Time limit exceeded
20	Execution timed out	5066 ms	20608 KB	Time limit exceeded