Submission #837005

#	Time	Username	Problem	Language	Result	Execution time	Memory
837005		ALeonidou	Catfish Farm (IOI22_fish)	C++17	23 / 100	117 ms	71480 KiB

fish

/*
IOI 2022 "Catfish" Solution for Subtask 4 (32%)
Time Complexity: O(N * Y^3)
*/

#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 N 100001
#define MAXC 5 // 5 cases

ll n,m;
long long dp[N+1][MAXC+1][MAXC+1];
vector <vii> arr;
vector <vi> s;

void printDP(ll l = 0, ll r = MAXC-1){
    for (ll k=l; k<=r; k++){
        cout<<"k: "<<k<<endl;
        for (ll i = 0; i<n; i++){
            cout<<i<<": ";
            for (ll j =0; j<MAXC; j++){
                cout<<dp[i][j][k];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
}

long long calc(ll u, ll l, ll r){ 
    long long sum = 0;
    for (ll i=0; i<sz(arr[u]); i++){
        if (arr[u][i].F >= l && arr[u][i].F <= r){
            sum += arr[u][i].S;
        }
    }
    return sum;
}

long long solve(){
    //prep line 0
    for (ll j =0; j<MAXC; j++){
        for (ll k =0; k<MAXC; k++){
            dp[0][j][k] = 0;
        }
    }
    
    //prep line 1
    for (ll j =0; j<MAXC; j++){
        for (ll k =0; k<MAXC; k++){
            ll new_j = s[1][j], new_k = s[0][k];
            if (new_j == new_k) dp[1][j][k] = 0;
            else if (new_j > new_k){
                dp[1][j][k] = calc(0, new_k+1, new_j);
            }
            else{
                dp[1][j][k] = calc(1, new_j+1, new_k);
            }
        }
    }

    // printDP();

    //solve
    for (ll i =2; i<n; i++){
        for (ll j = 0; j<MAXC; j++){
            for (ll k =0; k<MAXC; k++){
                long long ans = 0, c;
                ll new_j = s[i][j], new_k = s[i-1][k], new_y;
                
                if (new_j > new_k){
                    for (ll y = 0; y<MAXC; y++){
                        new_y = s[i-2][y];
                        if (new_y <= new_k){
                            c = dp[i-1][k][y] + calc(i-1,new_k+1,new_j);
                        }
                        else if (new_y < new_j){
                            c = dp[i-1][k][y] + calc(i-1,new_y+1,new_j);
                        }
                        else{
                            c = dp[i-1][k][y];
                        }
                        ans = max(ans, c);
                    }
                }
                else{   // j <= k
                    for (ll y = 0; y<MAXC; y++){
                        ans = max(ans, dp[i-1][k][y]);
                    }
                    if (new_j < new_k){
                        ans += calc(i, new_j+1, new_k);
                    }
                }
                dp[i][j][k] = ans;
            }
        }
    }

    // printDP();

    long long ans =0;
    for (ll i =0; i<n; i++){
        for (ll j =0; j<MAXC; j++){
            for (ll k =0; k<MAXC; k++){
                ans = max(ans, dp[i][j][k]);
            }
        }
    }

    return ans;
}

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

    //step 1:
    arr.assign(n, vii());
    for (ll i=0; i<m; i++){
        arr[X[i]].pb(ii(Y[i]+1, W[i]));
    }

    // for (ll i=0; i<2; i++){
    //     for (ll j = 0; j<n; j++){
    //         if (sz(arr[j]) > i) cout<<"("<<arr[j][i].F<<" "<<arr[j][i].S<<"), ";
    //         else cout<<"(-,-), ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;

    //step 2:
    s.assign(n, vi(5,0));
    for (ll i=0; i<n; i++){
        ll idx = 0;
        if (i != 0){
            for (ll j = 0; j<sz(arr[i-1]); j++){
                s[i][idx] = arr[i-1][j].F;
                idx++;
            }
        }
        if (i != n-1){
            for (ll j = 0; j<sz(arr[i+1]); j++){
                s[i][idx] = arr[i+1][j].F;
                idx++;
            }
        }
        sort(s[i].begin(), s[i].end());
    }

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

    long long ans = solve();
    return ans;
}

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