Submission #629889

#	Time	Username	Problem	Language	Result	Execution time	Memory
629889		peti1234	Catfish Farm (IOI22_fish)	C++17	100 / 100	255 ms	235884 KiB

fish

#include <bits/stdc++.h>

using namespace std;
const int c=3000005;
int n, m, si[c];
vector<pair<int, int> > sz[c];
vector<long long> dp0[c], dp1[c];
// 0 - megkapta a felette levoket, 1 - meg nem kapta meg

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n=N, m=M;
    for (int i=0; i<m; i++) {
        int a=X[i], b=Y[i], s=W[i];
        a++, b++;
        sz[a].push_back({b, s});
        //cout << "alap " << a << " " << b << " " << s << "\n";
    }
    for (int i=1; i<=n; i++) {
        sz[i].push_back({n+1, 0});
        sort(sz[i].begin(), sz[i].end());
        si[i]=sz[i].size();
        dp0[i].resize(si[i]), dp1[i].resize(si[i]);
    }
    for (int i=1; i<=n; i++) {
        int x=si[i-1], y=si[i];

        // 0->1
        long long maxi=0, sum=0, pos=0;
        for (int j=0; j<x; j++) {
            maxi=max(maxi, dp0[i-1][j]);
        }
        for (int j=0; j<y; j++) {
            dp1[i][j]=maxi;
        }

        // 1->1
        maxi=0, sum=0;
        for (int j=0; j<x; j++) {
            maxi=max(maxi, dp1[i-1][j]-sum);
            sum+=sz[i-1][j].second;
        }
        sum=0;
        for (int j=0; j<y; j++) {
            while (pos<x && sz[i][j].first>sz[i-1][pos].first) {
                sum+=sz[i-1][pos].second;
                pos++;
            }
            dp1[i][j]=max(dp1[i][j], maxi+sum);
        }


        // 0->0
        maxi=0, sum=0, pos=0;
        for (int j=0; j<x; j++) {
            while (pos<y && sz[i-1][j].first>sz[i][pos].first) {
                sum+=sz[i][pos].second;
                pos++;
            }
            maxi=max(maxi, dp0[i-1][j]+sum);
        }
        sum=0;
        for (int j=0; j<y; j++) {
            dp0[i][j]=maxi-sum;
            sum+=sz[i][j].second;
        }


        // 1->0 olyan, csak rosszabb lehet, mint az 1->1
        for (int j=0; j<y; j++) {
            dp0[i][j]=max(dp0[i][j], dp1[i][j]);
        }

        for (int j=0; j<y; j++) {
            //cout << i << " " << j << " " << dp0[i][j] << " " << dp1[i][j] << "\n";
        }
    }

    long long maxi=0;
    for (int j=0; j<si[n]; j++) {
        maxi=max(maxi, dp0[n][j]);
    }
    return maxi;
}
/*
int main()
{
    int n, m;
    vector<int> a, b, c;
    cin >> n >> m;
    for (int i=0; i<m; i++) {
        int aa, bb, cc;
        cin >> aa >> bb >> cc;
        a.push_back(aa), b.push_back(bb), c.push_back(cc);
    }
    cout << max_weights(n, m, a, b, c) << "\n";
    return 0;
}
*/
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

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