oj.uz

답안 #395086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395086 2021-04-27T17:45:01 Z MarcoMeijer 건포도 (IOI09_raisins) C++14
25 / 100
 5000 ms 26716 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 51;
const int N = (1<<20);

int n, m;
int cnt[MX][MX];
int dp[MX][MX][MX][MX];

int getDP(int l, int r, int u, int d) {
    if(dp[l][r][u][d] != -1) return dp[l][r][u][d];
    int res = 1e9;
    REP(x,l,r) res = min(res, getDP(l,x,u,d)+getDP(x+1,r,u,d));
    REP(y,u,d) res = min(res, getDP(l,r,u,y)+getDP(l,r,y+1,d));
    res += cnt[r+1][d+1] - cnt[l][d+1] - cnt[r+1][u] + cnt[l][u];
    if(l == r && u == d) res = 0; // we are done
    return res;
}

void program() {
    IN(n,m);
    RE(i,MX) RE(j,MX) cnt[i][j] = 0;
    RE(i,n) RE(j,m) cin>>cnt[i+1][j+1];
    RE(i,n+1) RE(j,m+1) {
        if(i   ) cnt[i][j] += cnt[i-1][j  ];
        if(   j) cnt[i][j] += cnt[i  ][j-1];
        if(i&&j) cnt[i][j] -= cnt[i-1][j-1];
    }
    memset(dp,-1,sizeof(dp));
    cout<<getDP(0,n-1,0,m-1)<<endl;
}

Subtask #1
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 26700 KB Output is correct
2 Correct 13 ms 26700 KB Output is correct
3 Correct 13 ms 26700 KB Output is correct
4 Correct 13 ms 26700 KB Output is correct
5 Correct 107 ms 26700 KB Output is correct
6 Execution timed out 5053 ms 26700 KB Time limit exceeded
7 Execution timed out 5040 ms 26700 KB Time limit exceeded
8 Execution timed out 5047 ms 26676 KB Time limit exceeded
9 Execution timed out 5030 ms 26716 KB Time limit exceeded
10 Execution timed out 5068 ms 26700 KB Time limit exceeded
11 Execution timed out 5071 ms 26700 KB Time limit exceeded
12 Execution timed out 5070 ms 26700 KB Time limit exceeded
13 Execution timed out 5068 ms 26700 KB Time limit exceeded
14 Execution timed out 5064 ms 26700 KB Time limit exceeded
15 Execution timed out 5068 ms 26700 KB Time limit exceeded
16 Execution timed out 5089 ms 26700 KB Time limit exceeded
17 Execution timed out 5078 ms 26700 KB Time limit exceeded
18 Execution timed out 5086 ms 26700 KB Time limit exceeded
19 Execution timed out 5089 ms 26700 KB Time limit exceeded
20 Execution timed out 5062 ms 26700 KB Time limit exceeded