제출 #835901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835901		ALeonidou	메기 농장 (IOI22_fish)	C++17	14 / 100	38 ms	8140 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 300
#define MAXY 9 // Y[i] + 1

ll n,m;
long long arr[N+1][MAXY+1];
long long dp[N+1][MAXY+1][MAXY+1];
long long s[N+1][MAXY+1];

void printDP(ll l = 0, ll r = MAXY){
    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<=MAXY; j++){
                cout<<dp[i][j][k];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
}

long long calc(ll u, ll l, ll r){       // 0 <= x <= 9
    l--, r--;
    if (l == 0){
        return s[u][r];
    }
    else{
        return s[u][r] - s[u][l-1];
    }
}

long long solve(){
    //prep line 0
    for (ll j =0; j<=MAXY; j++){
        for (ll k =0; k<=MAXY; k++){
            dp[0][j][k] = 0;
        }
    }

    //prep line 1
    for (ll j =0; j<=MAXY; j++){
        for (ll k =0; k<=MAXY; k++){
            if (j == k) dp[1][j][k] = 0;
            else if (j > k){
                dp[1][j][k] = calc(0, k+1, j);
            }
            else{
                dp[1][j][k] = calc(1, j+1, k);
            }
        }
    }

    // printDP();

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

    // printDP();

    long long ans =0;
    for (ll i =0; i<n; i++){
        for (ll j =0; j<=MAXY; j++){
            for (ll k =0; k<=MAXY; 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;

    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];
        }
    }

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

    long long ans = solve();

    return ans;
}

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