oj.uz

답안 #245339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245339 2020-07-06T04:39:45 Z Marlov 건포도 (IOI09_raisins) C++14
100 / 100
 442 ms 34552 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){
	return arr[x][y]-(a-1>=0?arr[a-1][y]:0)-(b-1>=0?arr[x][b-1]:0)+((b-1>=0&&a-1>=0)?arr[a-1][b-1]:0);
}

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];
			if(i>0) arr[i][j]+=arr[i-1][j];
			if(j>0) arr[i][j]+=arr[i][j-1];
			if(i>0&&j>0) arr[i][j]-=arr[i-1][j-1];
			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
100.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 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 5 ms 1152 KB Output is correct
8 Correct 8 ms 3456 KB Output is correct
9 Correct 10 ms 4992 KB Output is correct
10 Correct 12 ms 5888 KB Output is correct
11 Correct 11 ms 4992 KB Output is correct
12 Correct 35 ms 10624 KB Output is correct
13 Correct 60 ms 13824 KB Output is correct
14 Correct 15 ms 6144 KB Output is correct
15 Correct 76 ms 15488 KB Output is correct
16 Correct 10 ms 5376 KB Output is correct
17 Correct 32 ms 11264 KB Output is correct
18 Correct 224 ms 25976 KB Output is correct
19 Correct 380 ms 31992 KB Output is correct
20 Correct 442 ms 34552 KB Output is correct