oj.uz

답안 #245305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245305 2020-07-06T02:26:27 Z Marlov 건포도 (IOI09_raisins) C++14
85 / 100
 5000 ms 34560 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<long long,long long> pi;

#define maxV 51
#define INF 100000000
long long N,M;
long long arr[maxV][maxV];
long long dp[maxV][maxV][maxV][maxV];

long long psum(long long a,long long b,long long x,long long y){
	long long v=0;
	for(long long i=a;i<=x;i++){
		for(long long 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(long long i=0;i<N;i++){
		for(long long j=0;j<M;j++){
			for(long long a=i;a<N;a++){
				for(long long b=j;b<M;b++){
					dp[i][j][a][b]=INF;
				}
			}
		}
	}
	for(long long i=0;i<N;i++){
		for(long long j=0;j<M;j++){
			cin>>arr[i][j];
			dp[i][j][i][j]=0;
		}
	}
	//loc size
	for(long long a=0;a<N;a++){
		for(long long b=0;b<M;b++){
			//starting loc x,y
			for(long long x=0;x+a<N;x++){
				for(long long y=0;y+b<M;y++){
					//splits
					//1D
					for(long long 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(long long 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
	* long long overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1
85.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 6 ms 1152 KB Output is correct
8 Correct 49 ms 3516 KB Output is correct
9 Correct 105 ms 4992 KB Output is correct
10 Correct 177 ms 6012 KB Output is correct
11 Correct 142 ms 4992 KB Output is correct
12 Correct 877 ms 10704 KB Output is correct
13 Correct 1820 ms 13884 KB Output is correct
14 Correct 287 ms 6264 KB Output is correct
15 Correct 2399 ms 15524 KB Output is correct
16 Correct 79 ms 5496 KB Output is correct
17 Correct 716 ms 11264 KB Output is correct
18 Execution timed out 5074 ms 25856 KB Time limit exceeded
19 Execution timed out 5053 ms 31872 KB Time limit exceeded
20 Execution timed out 5071 ms 34560 KB Time limit exceeded