Submission #782185

#	Time	Username	Problem	Language	Result	Execution time	Memory
782185		Matblube	Raisins (IOI09_raisins)	C++14	100 / 100	681 ms	39824 KiB

raisins

#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 / 100