oj.uz

Submission #444808

# Submission time Handle Problem Language Result Execution time Memory
444808 2021-07-15T12:14:34 Z FEDIKUS Raisins (IOI09_raisins) C++17
100 / 100
 288 ms 24772 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

const int maxn=60;

int r[maxn][maxn];
int pref[maxn][maxn];
int memo[maxn][maxn][maxn][maxn];

inline int vr(int i,int j){
    if(i<0 || j<0) return 0;
    return pref[i][j];
}

inline int koliko(int i1,int j1,int i2,int j2){
    return vr(i2,j2)-vr(i2,j1-1)-vr(i1-1,j2)+vr(i1-1,j1-1);
}

int resi(int i1,int j1,int i2,int j2){
    if(i1==i2 && j1==j2) return 0;
    if(memo[i1][j1][i2][j2]!=0) return memo[i1][j1][i2][j2];
    int ret=INT_MAX;
    for(int i=i1;i<i2;i++){
        ret=min(ret,resi(i1,j1,i,j2)+resi(i+1,j1,i2,j2));
    }
    for(int j=j1;j<j2;j++){
        ret=min(ret,resi(i1,j1,i2,j)+resi(i1,j+1,i2,j2));
    }
    ret+=koliko(i1,j1,i2,j2);
    memo[i1][j1][i2][j2]=ret;
    return ret;
}

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin>>r[i][j];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            pref[i][j]=r[i][j];
            if(i!=0 || j!=0) pref[i][j]+=vr(i-1,j)+vr(i,j-1)-vr(i-1,j-1);
        }
    }
    cout<<resi(0,0,n-1,m-1);
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 6 ms 2764 KB Output is correct
9 Correct 9 ms 3820 KB Output is correct
10 Correct 11 ms 4556 KB Output is correct
11 Correct 10 ms 3916 KB Output is correct
12 Correct 30 ms 8008 KB Output is correct
13 Correct 49 ms 10244 KB Output is correct
14 Correct 17 ms 4916 KB Output is correct
15 Correct 58 ms 11344 KB Output is correct
16 Correct 7 ms 4172 KB Output is correct
17 Correct 29 ms 8268 KB Output is correct
18 Correct 149 ms 18684 KB Output is correct
19 Correct 239 ms 22944 KB Output is correct
20 Correct 288 ms 24772 KB Output is correct