제출 #1177804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177804		PagodePaiva	Catfish Farm (IOI22_fish)	C++20	14 / 100	95 ms	7936 KiB

fish

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

using namespace std;

const int N = 310;
const int MAXY = 10;

map <array <int, 3>, ll> dp;
ll mat[N][N];
ll pref[N][N];
vector <int> variacoes[N];

ll query(int a, int b, int c, int d){
    return pref[c][d] - pref[a-1][d]-pref[c][b-1]+pref[a-1][b-1];
}

ll calc(int i, int y1, int y2, int y3){
    if(y2+1 > max(y1, y3)) return 0;
    ll sum = query(i, y2+1, i, max(y1, y3));
    return sum;
}

ll valor_dp(int a, int b, int c){
    if(a == 0 and b == 0) return dp[{a, b, c}] = 0;
    if(dp.find({a, b, c}) != dp.end()) return -1e18;
    return dp[{a, b, c}];
}

ll solve(int i, int y2, int y3){
    if(i == 0){
        if(y2 == 0) return dp[{i, y2, y3}] = 0;
        return -1e18;
    }
    if(dp.find({i, y2, y3}) != dp.end()) return dp[{i, y2, y3}];
    dp[{i, y2, y3}] = -1e18;
    for(auto y1 : variacoes[i-1]){
        dp[{i, y2, y3}] = max(dp[{i, y2, y3}], solve(i-1, y1, y2) +calc(i, y1, y2, y3));
    }
    return dp[{i, y2, y3}];
}

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for(int i = 0;i < m;i++){
        mat[X[i]+1][Y[i]+1] = W[i];
        variacoes[X[i]+1].push_back(Y[i]+1);
        variacoes[X[i]+2].push_back(Y[i]+1);
        variacoes[X[i]].push_back(Y[i]+1);
    }
    for(int i = 1;i < N;i++){
        for(int j = 1;j < N;j++){
            pref[i][j] = pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+mat[i][j];
        }
    }
    variacoes[0].clear();
    for(int i = 0;i < N;i++){
        variacoes[i].push_back(0);
    }
    ll ans = 0;
    for(int y1 = 0;y1 < MAXY;y1++){
        for(int y2 = 0;y2 < MAXY;y2++){
            ans = max(ans, solve(n, y2, 0));
        }
    }
    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