제출 #763308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763308		raysh07	Catfish Farm (IOI22_fish)	C++17	14 / 100	60 ms	143588 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (int)(1e18)

const int N = 3005;
long long a[N][N];
long long dp[N][N][2];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    if (n > 3000) return 0LL;
    
    for (int i = 0; i < m; i++){
        a[x[i] + 1][y[i] + 1] += w[i];
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            a[i][j] += a[i][j - 1];
        }
    }
    
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            dp[i][j][0] = dp[i][j][1] = -INF;
        }
    }
    
    dp[0][0][1] = 0; //0, 1 --> not processed / processed row 
    for (int i = 1; i <= n + 1; i++){
        //0--> inc, 1--> dec when not 0 
        
        //start bitonic sequence
        if (i != (n + 1)){
        for (int j = 1; j <= n; j++){
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][0][0] + a[i - 1][j] - a[i][j]);
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][0][1] - a[i][j]);
        }
        
        //continue bitonic --> increasing 
        long long mx = -INF;
        for (int j = 1; j <= n; j++){
            mx = max(mx, dp[i - 1][j][0]);
            dp[i][j][0] = max(dp[i][j][0], mx - a[i][j] + a[i - 1][j]);
        }
        
        mx = -INF;
        for (int j = n; j >= 1; j--){
            mx = max(mx, dp[i - 1][j][1]);
            dp[i][j][1] = max(dp[i][j][1], mx - a[i][j] + a[i + 1][j]);
        }
        
        //switch from inc to dec 
        for (int j = 1; j <= n; j++){
            dp[i][j][1] = max(dp[i][j][1], dp[i][j][0] + a[i][j] + a[i + 1][j]);
        }
        }
        
        //end bitonic 
        for (int j = 1; j <= n; j++){
            dp[i][0][0] = max(dp[i][0][0], dp[i - 1][j][1] - a[i][j]);
            dp[i][0][1] = max(dp[i][0][1], dp[i - 1][j][1]);
        }
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][0]);
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][1]);
    }
    
    long long ans = -INF;
    ans = max(ans, dp[n + 1][0][0]);
    ans = max(ans, dp[n + 1][0][1]);
    return ans;
}

// int main(){
//     int n, m; cin >> n >> m;
    
//     vector <int> a(m), b(m), c(m);
//     for (auto &x : a) cin >> x;
//     for (auto &x : b) cin >> x;
//     for (auto &x : c) cin >> x;
    
//     cout << max_weights(n, m, a, b, c) << "\n";
//     return 0;
// }

• 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