Submission #629884

#	Time	Username	Problem	Language	Result	Execution time	Memory
629884		peti1234	Catfish Farm (IOI22_fish)	C++17	0 / 100	400 ms	477408 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});
    }
    for (int i=0; i<=n+1; 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+1; 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][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]);
        }
    }


    return dp0[n+1][0];
}
/*
int main()
{

    return 0;
}
*/

• 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