oj.uz

답안 #245303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245303 2020-07-06T02:24:39 Z Marlov 건포도 (IOI09_raisins) C++14
15 / 100
 5000 ms 20608 KB 
/*
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

# 결과 실행 시간 메모리 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