Submission #245303

#TimeUsernameProblemLanguageResultExecution timeMemory
245303MarlovRaisins (IOI09_raisins)C++14
15 / 100
5075 ms20608 KiB
/* 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...