Submission #863799

#TimeUsernameProblemLanguageResultExecution timeMemory
863799AtabayRajabliRaisins (IOI09_raisins)C++17
100 / 100
266 ms72280 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // author : AtabeyR #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define all(v) v.begin(), v.end() #define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define sec second #define fi first #define int ll #define print(k) cerr << "Ans : "; cout << k << endl; #define ins insert #define bpc __builtin_popcountll #define skip continue #define endll '\n' #define gcd(a, b) __gcd(a, b) #define lcm(a, b) a*b / (__gcd(a, b)) typedef long long ll; typedef unsigned long long ull; const int oo = 0x3F3F3F3F; const int ooo = 0x3F3F3F3F3F3F3F3FLL; const int mod = 998244353; const int sz = 55; using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>; void open(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } int n, m, k, a[sz][sz], pref[sz][sz], dp[sz][sz][sz][sz]; int cost(int x1, int y1, int x2, int y2) { return pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]; } int f(int x1, int y1, int x2, int y2) { if(x1 == x2 && y1 == y2) return 0; if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2]; int mn = ooo; for(int i = y1; i<y2; i++) mn = min(mn, f(x1, y1, x2, i) + f(x1, i+1, x2, y2) + cost(x1, y1, x2, y2)); for(int j = x1; j<x2; j++) mn = min(mn, f(x1, y1, j, y2) + f(j+1, y1, x2, y2) + cost(x1, y1, x2, y2)); return dp[x1][y1][x2][y2] = mn; } void solve() { cin >> n >> m; for(int i = 1; i<=n; i++) for(int j = 1; j<=m; j++ )cin >> a[i][j]; for(int i = 1; i<=n; i++) for(int j = 1; j<=m; j++) pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + a[i][j]; memset(dp, -1, sizeof(dp)); cout << f(1, 1, n, m) << endl; } int32_t main() { // open("i"); OPT int t = 1; //cin >> t; for(int i = 1; i<=t; i++) solve(); }

Compilation message (stderr)

raisins.cpp: In function 'void open(std::string)':
raisins.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raisins.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...