oj.uz

답안 #940827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940827 2024-03-07T17:27:14 Z whatthemomooofun1729 건포도 (IOI09_raisins) C++14
100 / 100
 123 ms 26968 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <sstream>
#include <chrono>
#include <random>

#define ff first
#define ss second
#define ll long long
#define ld long double
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define EB emplace_back
#define PoB pop_back
#define LOG log2
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define fch(t, v) for (auto t : v)
#define sz(x) int(x.size())
#define rsz resize
#define gp(x) vector<vector<x>>
#define btree vector<pii>
#define vll vector<ll>
#define Max(a, b, c) max(max(a,b),c)
#define fMax(a, b, c, d) max(Max(a, b, c), dp)
#define Min(a, b, c) min(min(a,b),c)
#define Mid(a, b, c) max(min(a, b), min(max(a, b), c))
#define st(a) set<a>
#define gi greater<int>
#define all(x) (x).begin(),(x).end()
#define tri(x) tuple<x,x,x>
#define pil pair<int, long>
#define ull unsigned long long
#define eps 1e-9
//#define debug(x) cout << '>' << #x << ':' << x << endl;

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
void println() {cerr << ">--------------------<" << endl;}
void printm(vector<vector<int>>& mat) {
    cerr << "matrix: " << endl;
    for (int i = 0; i<(int)mat.size(); i++) {for (int j = 0; j<(int)mat[0].size(); j++) {cerr << mat[i][j] << " ";} cerr << endl;}
}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

// templates
template <class T> bool ckmin(T &a, const T &b) {return b<a ? a = b, 1 : 0;}
template <class T> bool ckmax(T &a, const T &b) {return b>a ? a = b, 1 : 0;}
template <class T> using gr = greater<T>;
mt19937_64 rng_ll(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using vc = vector<T>;
template <class T> using p_q = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vc<T>, gr<T>>;
template <class T1, class T2> using pr = pair<T1, T2>;
int rng(int M) {return (int)(rng_ll()%M);}

constexpr int INF = (int)2e9;
constexpr int MOD = 998244353;
constexpr ll LL_INF = (ll)3e18;
constexpr int mod = (int)1e9 + 7;
constexpr ll inverse = 500000004LL; // inverse of 2 modulo 1e9 + 7

void setIO(const string& str) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (str.empty()) return;
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}

int N, M;
int grid[51][51], psum[51][51];
int dp[51][51][51][51];

int w(int x1, int y1, int x2, int y2) {
    return psum[x2][y2] - (y1 > 0 ? psum[x2][y1-1] : 0) - (x1 > 0 ? psum[x1-1][y2] : 0) + (y1 > 0 && x1 > 0 ? psum[x1-1][y1-1] : 0);
}

int main() { // TIME YOURSELF !!!
    setIO("");
    cin >> N >> M;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            psum[i][j] = (i > 0 ? psum[i-1][j] : 0) + (j > 0 ? psum[i][j-1] : 0) - (i > 0 && j > 0 ? psum[i-1][j-1] : 0) + grid[i][j];
        }
    }
    for (int i = N-1; i >= 0; --i) {
        for (int j = M-1; j >= 0; --j) {
            for (int k = i; k < N; ++k) {
                for (int l = j; l < M; ++l) {
                    if (k == i && l == j) {
                        dp[i][j][k][l] = 0;
                        continue;
                    }
                    int weight = w(i, j, k, l);
                    for (int m = i; m < k; ++m) {
                        ckmin(dp[i][j][k][l], dp[i][j][m][l] + weight + dp[m+1][j][k][l]);
                    }
                    for (int m = j; m < l; ++m) {
                        ckmin(dp[i][j][k][l], weight + dp[i][j][k][m] + dp[i][m+1][k][l]);
                    }
                }
            }
        }
    }
    cout << dp[0][0][N-1][M-1];
    return 0;
}

// CHECK LONG LONGS, binary search on ans?
// 5000 * 5000 size matrices are kinda big (potential mle)
// Do something, start simpler
// IBM motto: THINK

Compilation message

raisins.cpp: In function 'void setIO(const string&)':
raisins.cpp:115:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raisins.cpp:116:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 5 ms 26716 KB Output is correct
3 Correct 4 ms 26772 KB Output is correct
4 Correct 5 ms 26836 KB Output is correct
5 Correct 4 ms 26716 KB Output is correct
6 Correct 5 ms 26716 KB Output is correct
7 Correct 5 ms 26832 KB Output is correct
8 Correct 5 ms 26836 KB Output is correct
9 Correct 7 ms 26956 KB Output is correct
10 Correct 8 ms 26780 KB Output is correct
11 Correct 8 ms 26716 KB Output is correct
12 Correct 15 ms 26796 KB Output is correct
13 Correct 20 ms 26968 KB Output is correct
14 Correct 9 ms 26716 KB Output is correct
15 Correct 26 ms 26964 KB Output is correct
16 Correct 6 ms 26932 KB Output is correct
17 Correct 12 ms 26712 KB Output is correct
18 Correct 74 ms 26956 KB Output is correct
19 Correct 91 ms 26948 KB Output is correct
20 Correct 123 ms 26840 KB Output is correct