oj.uz

Submission #444809

# Submission time Handle Problem Language Result Execution time Memory
444809 2021-07-15T12:15:01 Z FEDIKUS Raisins (IOI09_raisins) C++17
100 / 100
 299 ms 24900 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 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 0 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 3788 KB Output is correct
10 Correct 12 ms 4556 KB Output is correct
11 Correct 11 ms 3916 KB Output is correct
12 Correct 34 ms 8000 KB Output is correct
13 Correct 54 ms 10308 KB Output is correct
14 Correct 16 ms 4924 KB Output is correct
15 Correct 73 ms 11392 KB Output is correct
16 Correct 8 ms 4172 KB Output is correct
17 Correct 33 ms 8260 KB Output is correct
18 Correct 163 ms 18716 KB Output is correct
19 Correct 261 ms 23016 KB Output is correct
20 Correct 299 ms 24900 KB Output is correct