oj.uz

Submission #782185

# Submission time Handle Problem Language Result Execution time Memory
782185 2023-07-13T16:10:32 Z Matblube Raisins (IOI09_raisins) C++14
100 / 100
 681 ms 39824 KB 
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
#define fr(i, x) for(ll i=0 ; i<x ; i++)
#define fra(x, v) for(auto x:v)
#define fra1(x,v) for(auto &x:v)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define pb(x) push_back(x)
#define F first
#define S second
#define inf 10000000000
#define sz(x) (ll) x.size()

const double PI=acos(-1);
const ll MOD=1e9+7, maxN=100010;

struct uwu{
    ll x ,y, z;
};

ll gcd(ll a, ll b){return (!b)?a:(gcd(b, a%b));}

ll lcm(ll a, ll b){
    if(a>b) swap(a, b);
    return a/gcd(a, b)*b;
}

ll binpow(ll a, ll b){
    ll cc=1;
    while(b){
        if(b&1) cc*=a;
        a*=a;
        b>>=1;
    }
    return cc;
}
ll binpow1(ll a, ll b){
    ll cc=1;
    while(b){
        if(b&1) cc=cc*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return cc%MOD;
}

ll xd[50][50];
ll dp[50][50][50][50];
bool use[50][50][50][50];

ll uwu(ll a, ll b, ll c, ll d){
    if(a==c && b==d) return 0;
    if(use[a][b][c][d]) return dp[a][b][c][d];
    else use[a][b][c][d]=1;
    ll aux=inf, lauritauwu=0;
    for(ll i=a ; i<=c ; i++){
        for(ll j=b ; j<=d ; j++) lauritauwu+=xd[i][j];
    }
    ll l1, l2;
    for(ll i=a+1 ; i<=c ; i++){
        l1=uwu(a, b, i-1, d);
        l2=uwu(i, b, c, d);
        aux=min(aux, l1+l2+lauritauwu);
    }
    for(ll i=b+1 ; i<=d ; i++){
        l1=uwu(a, b, c, i-1);
        l2=uwu(a, i, c, d);
        aux=min(aux, l1+l2+lauritauwu);
    }
    dp[a][b][c][d]=aux;
    return aux;
}

void solve(){
    ll n, m; cin>>n>>m;
    fr(i, n){
        fr(j, m) cin>>xd[i][j];
    }
    cout<<uwu(0, 0, n-1, m-1)<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 9 ms 4432 KB Output is correct
9 Correct 17 ms 6216 KB Output is correct
10 Correct 19 ms 7380 KB Output is correct
11 Correct 16 ms 6360 KB Output is correct
12 Correct 56 ms 12884 KB Output is correct
13 Correct 96 ms 16592 KB Output is correct
14 Correct 32 ms 7756 KB Output is correct
15 Correct 120 ms 18516 KB Output is correct
16 Correct 11 ms 6428 KB Output is correct
17 Correct 46 ms 13260 KB Output is correct
18 Correct 365 ms 30132 KB Output is correct
19 Correct 528 ms 36964 KB Output is correct
20 Correct 681 ms 39824 KB Output is correct