Submission #398058

#TimeUsernameProblemLanguageResultExecution timeMemory
398058ak2006Raisins (IOI09_raisins)C++14
100 / 100
254 ms33100 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //int solve(int x1,int y1,int x2,int y2,vvvvi&dp) //{ // if (dp[x1][y1][x2][y2] != -1)return dp[x1][y1][x2][y2]; // //} int main() { int n,m; cin>>n>>m; vvi g(n + 1,vi(m + 1)),p(n + 1,vi(m + 1)); vvvvi dp(n + 1,vvvi(m + 1,vvi(n + 1,vi(m + 1,1e9)))); for (int i = 1;i<=n;i++){ for (int j = 1;j<=m;j++){ cin>>g[i][j]; p[i][j] = g[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1]; } } for (int x1 = n; x1 >= 1 ; x1--){ for (int y1 = m; y1 >= 1 ; y1--){ for (int x2 = x1; x2 <= n ;x2++){ for (int y2 = y1; y2 <= m ;y2++){ dp[x1][y1][x2][y2] = 1e9; if (x1 == x2 && y1 == y2)dp[x1][y1][x2][y2] = 0; int val = p[x2][y2] + p[x1 - 1][y1 - 1] - p[x2][y1 - 1] - p[x1 - 1][y2]; for (int x = x1; x < x2 ;x++) dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2],val + dp[x1][y1][x][y2] + dp[x + 1][y1][x2][y2]); for (int y = y1; y < y2 ;y++) dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2],val + dp[x1][y1][x2][y] + dp[x1][y + 1][x2][y2]); } } } } cout<<dp[1][1][n][m]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...