oj.uz

Submission #444807

# Submission time Handle Problem Language Result Execution time Memory
444807 2021-07-15T12:12:19 Z FEDIKUS Raisins (IOI09_raisins) C++17
25 / 100
 5000 ms 2116 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
25.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 61 ms 656 KB Output is correct
6 Execution timed out 5083 ms 904 KB Time limit exceeded
7 Execution timed out 5060 ms 844 KB Time limit exceeded
8 Execution timed out 5067 ms 520 KB Time limit exceeded
9 Execution timed out 5085 ms 396 KB Time limit exceeded
10 Execution timed out 5093 ms 452 KB Time limit exceeded
11 Execution timed out 5048 ms 396 KB Time limit exceeded
12 Execution timed out 5077 ms 452 KB Time limit exceeded
13 Execution timed out 5044 ms 460 KB Time limit exceeded
14 Execution timed out 5056 ms 516 KB Time limit exceeded
15 Execution timed out 5088 ms 452 KB Time limit exceeded
16 Execution timed out 5060 ms 2116 KB Time limit exceeded
17 Execution timed out 5081 ms 524 KB Time limit exceeded
18 Execution timed out 5095 ms 408 KB Time limit exceeded
19 Execution timed out 5084 ms 408 KB Time limit exceeded
20 Execution timed out 5072 ms 460 KB Time limit exceeded