oj.uz

Submission #444806

# Submission time Handle Problem Language Result Execution time Memory
444806 2021-07-15T12:11:39 Z FEDIKUS Raisins (IOI09_raisins) C++17
100 / 100
 309 ms 24860 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];

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

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 1 ms 320 KB Output is correct
2 Correct 1 ms 324 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 2752 KB Output is correct
9 Correct 9 ms 3888 KB Output is correct
10 Correct 13 ms 4556 KB Output is correct
11 Correct 11 ms 4004 KB Output is correct
12 Correct 33 ms 8004 KB Output is correct
13 Correct 53 ms 10204 KB Output is correct
14 Correct 16 ms 4900 KB Output is correct
15 Correct 68 ms 11408 KB Output is correct
16 Correct 8 ms 4092 KB Output is correct
17 Correct 29 ms 8268 KB Output is correct
18 Correct 169 ms 18884 KB Output is correct
19 Correct 259 ms 22956 KB Output is correct
20 Correct 309 ms 24860 KB Output is correct