Submission #835483

#	Time	Username	Problem	Language	Result	Execution time	Memory
835483		ALeonidou	Catfish Farm (IOI22_fish)	C++17	0 / 100	21 ms	5584 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

typedef vector <ll> vi;
typedef vector <long long > vl;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;


void printVct(vl &v, string s = ""){
    cout<<s<<": ";
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

#define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl;


#define MAXN 300
#define MAXY 9 // Y[i] + 1

ll n,m;
long long arr[MAXN+1][MAXY+1];
long long dp[MAXN+1][MAXY+1][MAXY+1];
long long s[MAXN+1][MAXY+1];
void tabb(ll n) {
    for (ll i=0; i<n; i++) cout<<"\t";
}

long long calc(ll u, ll l, ll r){       // 0 <= x <= 9
    
    if (u < 0){
        cout<<"ERROR!! "<<u<<" "<<l<<" "<<r<<endl<<endl;
        exit(1);
    }

    if (l > r){
        return 0;
    }
    l--, r--;
    if (l == 0){
        return s[u][r];
    }
    else{
        return s[u][r] - s[u][l-1];
    }
}

long long solve(ll i, ll j, ll k){
    // dbg3(i,j,k);
    //base case
    if (i < 0) return 0;

    //general case
    if (dp[i][j][k] == -1){
        long long ans = 0,c;
        for (ll y =0; y<=j; y++){
            // dbg(y);
            c = solve(i-1,k,y) + calc(i-1, max(y,k+1), j);      //chek indexes
            ans=max(ans, c);
        }

        for (ll y =j+1; y<=MAXY; y++){
            c = solve(i-1,k,y);
            ans = max(ans, c);
        }

        dp[i][j][k] = ans;
    }

    return dp[i][j][k];
}

long long init_solve(){
    ll b;
    for (ll i=0;i<n;i++){
        if (i == 0) b = 0;
        else b = -1;
        for (ll j =0;j <=MAXY; j++){
            for (ll k =0; k<=MAXY; k++){
                dp[i][j][k] = b;
            }
        }
    }

    long long ans =0 ;
    for (ll i=0; i<=MAXY; i++){
        for (ll j =0; j<=MAXY; j++){
            ans = max(ans, solve(n-1,i,j));
        }
    }

    return ans;
}

long long max_weights(int N, int M, vi X, vi Y, vi W) {
    n= N, m =M;

    for (ll i =0 ; i<m; i++){
        arr[X[i]][Y[i]] = W[i];
    }

    for (ll i =0; i<n; i++){
        s[i][0] = arr[i][0];
        for (ll j = 1; j< MAXY; j++){
            s[i][j] =s[i][j-1] + arr[i][j-1];
        }
    }

    // printArr2D(s,n,MAXY,"s");

    // dbg3(calc(0,3,5), calc(2, 1, 4), calc(4, 3, 8));

    long long ans = init_solve();

    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16