제출 #1177806

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

fish

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

using namespace std;

const int N = 310;

ll dp[N][N][N];
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 solve(int i, int y2, int y3){
    if(i == 0){
        if(y2 == 0) return dp[i][y2][y3] = 0;
        return dp[i][y2][y3] = -1e18;
    }
    if(dp[i][y2][y3] != -1) 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) {
    memset(dp, -1, sizeof dp);
    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 y2 = 0;y2 < N;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