oj.uz

Submission #395085

# Submission time Handle Problem Language Result Execution time Memory
395085 2021-04-27T17:42:48 Z MarcoMeijer Raisins (IOI09_raisins) C++14
25 / 100
 5000 ms 26828 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 getRegion(int l, int r, int u, int d) {
    r++; d++;
    return cnt[r][d] - cnt[l][d] - cnt[r][u] + cnt[l][u];
}
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 += getRegion(l,r,u,d);
    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];
    }
    RE(i,MX) RE(j,MX) RE(k,MX) RE(l,MX) dp[i][j][k][l] = -1;
    cout<<getDP(0,n-1,0,m-1)<<endl;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26700 KB Output is correct
2 Correct 17 ms 26812 KB Output is correct
3 Correct 17 ms 26704 KB Output is correct
4 Correct 18 ms 26700 KB Output is correct
5 Correct 132 ms 26784 KB Output is correct
6 Execution timed out 5083 ms 26828 KB Time limit exceeded
7 Execution timed out 5093 ms 26700 KB Time limit exceeded
8 Execution timed out 5094 ms 26696 KB Time limit exceeded
9 Execution timed out 5097 ms 26700 KB Time limit exceeded
10 Execution timed out 5088 ms 26700 KB Time limit exceeded
11 Execution timed out 5091 ms 26700 KB Time limit exceeded
12 Execution timed out 5084 ms 26700 KB Time limit exceeded
13 Execution timed out 5095 ms 26700 KB Time limit exceeded
14 Execution timed out 5055 ms 26700 KB Time limit exceeded
15 Execution timed out 5094 ms 26700 KB Time limit exceeded
16 Execution timed out 5084 ms 26700 KB Time limit exceeded
17 Execution timed out 5093 ms 26700 KB Time limit exceeded
18 Execution timed out 5067 ms 26700 KB Time limit exceeded
19 Execution timed out 5094 ms 26700 KB Time limit exceeded
20 Execution timed out 5097 ms 26688 KB Time limit exceeded