제출 #1320695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320695		ezzzay	메기 농장 (IOI22_fish)	C++17	0 / 100	1010 ms	2162688 KiB

fish

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back

vector<pair<int,int>> vc[310];

long long max_weights(int N, int M,
                      vector<int> X,
                      vector<int> Y,
                      vector<int> W) {

    vector<vector<ll>> dp(N+2, vector<ll>(N+2, 0));
    vector<vector<ll>> ps(N+2, vector<ll>(N+2, 0));

    for(int i = 0; i <= N; i++) vc[i].clear();

    for(int i = 0; i < M; i++){
        vc[X[i] + 1].pb({Y[i] + 1, W[i]});
    }

    // 🔴 REQUIRED: sort by Y
    for(int i = 1; i <= N; i++){
        sort(vc[i].begin(), vc[i].end());
    }

    ll mx = 0;

    for(int i = 1; i <= N; i++){
        int idx = 0;

        // build prefix sums for row i
        for(int l = 1; l <= N; l++){
            ps[i][l] = ps[i][l-1];
            while(idx < (int)vc[i].size() && vc[i][idx].ff <= l){
                ps[i][l] += vc[i][idx].ss;
                idx++;
            }
        }

        // DP transitions
        for(int j = 0; j <= N; j++){
            int l = min(i, j);
            int r = max(i, j);

            dp[i][j] = max(dp[i][j],
                            dp[i-1][j] + ps[i-1][r] - ps[i-1][l-1]);

            if(i >= 2){
                dp[i][j] = max(dp[i][j],
                                dp[i-2][j] + ps[i-1][r]);
            }

            mx = max(mx, dp[i][j]);
        }
    }

    return mx;
}

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