Submission #630057

#	Time	Username	Problem	Language	Result	Execution time	Memory
630057		garam1732	Catfish Farm (IOI22_fish)	C++17	100 / 100	397 ms	61056 KiB

fish

#include "fish.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

const int MAXN = 100100;
typedef long long ll;
typedef pair<int, int> pi;

vector<pi> c[MAXN];
vector<int> fish[MAXN];
vector<ll> sum[MAXN], dp[MAXN][3], a[4];

//        a[0][0] = dp[i][0][2] + sum[i+1][0];
//        a[0][1] = LLONG_MIN;
//        a[0][2] = dp[i-1][0][2];
//        a[0][3] = dp[i-1][0][2] + sum[i][0];
//        for(int j = 1; j <= N; j++) {
//            a[j][0] = max(a[j-1][0], dp[i][j][2] + sum[i+1][j]);
//            a[j][1] = max(a[j-1][1], dp[i][j][0] - sum[i][j]);
//            a[j][2] = max(a[j-1][2], dp[i-1][j][2]);
//            a[j][3] = max(a[j-1][3], dp[i-1][j][2] + sum[i][j]);
//        }
//
//        b[N][0] = dp[i][N][2] + sum[i+1][N];
//        b[N][1] = dp[i][N][0] - sum[i][N];
//        b[N][2] = dp[i-1][N][2];
//        b[N][3] = dp[i-1][N][2] + sum[i][N];
//        for(int j = N-1; j >= 0; j--) {
//            b[j][0] = max(b[j+1][0], dp[i][j][2] + sum[i+1][j]);
//            b[j][1] = max(b[j+1][1], dp[i][j][0] - sum[i][j]);
//            b[j][2] = max(b[j+1][2], dp[i-1][j][2]);
//            b[j][3] = max(b[j+1][3], dp[i-1][j][2] + sum[i][j]);
//        }

void f(int i, int N) {
    int it2;
    if(i+1 < N) {
        it2 = upper_bound(c[i+1].begin(), c[i+1].end(), pi(*fish[i].rbegin(), INT_MAX)) - c[i+1].begin();
        a[0].push_back(dp[i][2][(int)fish[i].size()-1] + sum[i+1][it2]);
        for(int j = (int)fish[i].size()-2; j >= 0; j--) {
            it2 = upper_bound(c[i+1].begin(), c[i+1].end(), pi(fish[i][j], INT_MAX)) - c[i+1].begin();
            a[0].push_back(max(*a[0].rbegin(), dp[i][2][j] + sum[i+1][it2]));
        }

        reverse(a[0].begin(), a[0].end());
    }

    it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i][0], INT_MAX)) - c[i].begin();
    a[1].push_back(dp[i][0][0] - sum[i][it2]);
    for(int j = 1; j < fish[i].size(); j++) {
        it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i][j], INT_MAX)) - c[i].begin();
        a[1].push_back(max(*a[1].rbegin(), dp[i][0][j] - sum[i][it2]));
    }

    if(i) {
        a[2].push_back(dp[i-1][2][0]);
        for(int j = 1; j < fish[i-1].size(); j++) {
            a[2].push_back(max(*a[2].rbegin(), dp[i-1][2][j]));
        }

        it2 = upper_bound(c[i].begin(), c[i].end(), pi(*fish[i-1].rbegin(), INT_MAX)) - c[i].begin();
        a[3].push_back(dp[i-1][2][(int)fish[i-1].size()-1] + sum[i][it2]);
        for(int j = (int)fish[i-1].size()-2; j >= 0; j--) {
            it2 = upper_bound(c[i].begin(), c[i].end(), pi(fish[i-1][j], INT_MAX)) - c[i].begin();
            a[3].push_back(max(*a[3].rbegin(), dp[i-1][2][j] + sum[i][it2]));
        }
        reverse(a[3].begin(), a[3].end());
    }
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for(int i = 0; i < M; i++) {
        c[X[i]].push_back(pi(Y[i]+1, W[i]));
    }

    for(int i = 0; i < N; i++) sort(c[i].begin(), c[i].end());
    for(int i = 0; i < N; i++) {
        fish[i].push_back(0);
        if(i) for(pi j : c[i-1]) fish[i].push_back(j.first);
        if(i+1 < N) for(pi j : c[i+1]) fish[i].push_back(j.first);

        sort(fish[i].begin(), fish[i].end());
        fish[i].erase(unique(fish[i].begin(), fish[i].end()), fish[i].end());
    }

    for(int i = 0; i < N; i++) {
        sum[i].push_back(0);
        for(pi t : c[i]) sum[i].push_back(*sum[i].rbegin()+t.second);
    }

//    for(int i = 0; i < N; i++)
//        for(pi t : c[i]) cout<<t.first<<" "<<t.second<<" ";
//    cout<<endl;
//    for(int i = 0; i < N; i++) {
//        for(int t : fish[i]) cout<<t<<" ";
//        cout<<endl;
//    }
//    cout<<endl;
//    for(int i = 0; i < N; i++) {
//        for(int t : sum[i]) cout<<t<<" ";
//        cout<<endl;
//    }
//    cout<<endl;

//    for(int j = 0; j <= N; j++) {
//        for(int k = j; k <= N; k++) {
//            dp[2][j][1] = max(dp[2][j][1], sum[2][k] - sum[2][j]);
//        }
//        for(int k = 0; k < j; k++) {
//            dp[2][j][0] = max(dp[2][j][0], sum[1][j] - sum[1][k]);
//        }
//
//        dp[2][j][2] = max(dp[2][j][0], dp[2][j][1]);
//    }

//    for(int j = 0; j <= N; j++) {
//        update(1, 0, N, j, dp[2][j][2] + sum[3][j], 0);
//        update(1, 0, N, j, dp[2][j][0] - sum[2][j], 1);
//        update(1, 0, N, j, dp[1][j][2], 2);
//        update(1, 0, N, j, dp[1][j][2] + sum[2][j], 3);
//    }
//    a[0][1] = LLONG_MIN;
//    a[0][2] = dp[1][0][2];
//    for(int j = 1; j <= N; j++) {
//        a[j][1] = max(a[j-1][1], dp[2][j][0] - sum[2][j]);
//        a[j][2] = max(a[j-1][2], dp[1][j][2]);
//    }
//
//    a[N][0] = dp[2][N][2] + sum[3][N];
//    a[N][3] = dp[1][N][2] + sum[2][N];
//    for(int j = N-1; j >= 0; j--) {
//        a[j][0] = max(a[j+1][0], dp[2][j][2] + sum[3][j]);
//        a[j][3] = max(a[j+1][3], dp[1][j][2] + sum[2][j]);
//    }
    for(int t : fish[0]) for(int j = 0; j < 3; j++) dp[0][j].push_back(0);

    f(0, N);

    int it1, it2;
    for(int i = 1; i < N; i++) {
        for(int k = 0; k < 3; k++) dp[i][k].resize(fish[i].size());
        for(int j = 0; j < fish[i].size(); j++) {
//            for(int k = j; k <= N; k++) {
//                //dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][2] + sum[i][k] - sum[i][j]);
//                //if(i==N&&j==N-1)cout<<dp[i][j]<<" ";
//            }
            //dp[i][j][1] = solve(1, 0, N, j, N, 0) - sum[i][j];
            int v = fish[i][j];
            it1 = lower_bound(fish[i-1].begin(), fish[i-1].end(), v) - fish[i-1].begin();
            it2 = upper_bound(c[i].begin(), c[i].end(), pi(v, INT_MAX)) - c[i].begin();
            if(it1 < fish[i-1].size()) dp[i][1][j] = a[0][it1] - sum[i][it2];
            //cout<<endl;
//            for(int k = 1; k < j; k++) {
//                dp[i][j][0] = max(dp[i][j][0], dp[i-1][k][0] + sum[i-1][j] - sum[i-1][k]);
//                if(i==N&&j==N-1) cout<<dp[i][j]<<" ";
//            }
            //dp[i][j][0] = solve(1, 0, N, 1, j-1, 1) + sum[i-1][j];
            dp[i][0][j] = 0;

            //it1 = upper_bound(fish[i-1].begin(), fish[i-1].end(), j) - fish[i-1].begin();
            it2 = upper_bound(c[i-1].begin(), c[i-1].end(), pi(v, INT_MAX)) - c[i-1].begin();
            if(it1) dp[i][0][j] = a[1][it1-1] + sum[i-1][it2];
            //cout<<endl;
            //for(int k = 0; k <= N; k++) {
                //dp[i][j][0] = max(dp[i][j][0], dp[i-2][k][2] + sum[i-1][max(k, j)]);
                //if(i==N&&j==N-1) cout<<dp[i][j]<<" ";
            //}
            //dp[i][j][0] = max(dp[i][j][0], solve(1, 0, N, 0, j, 2) + sum[i-1][j]);
            if(i > 1) {
                it1 = upper_bound(fish[i-2].begin(), fish[i-2].end(), v) - fish[i-2].begin();
                if(it1) dp[i][0][j] = max(dp[i][0][j], a[2][it1-1] + sum[i-1][it2]);
                //dp[i][j][0] = max(dp[i][j][0], solve(1, 0, N, j+1, N, 3));
                //it1 = lower_bound(fish[i-2].begin(), fish[i-2].end(), j) - fish[i-2].begin();
                if(it1 < fish[i-2].size()) dp[i][0][j] = max(dp[i][0][j], a[3][it1]);
            }

            dp[i][2][j] = max(dp[i][0][j], dp[i][1][j]);
//            cout<<i<<" "<<j<<endl;
//            for(int t = 0; t<3;t++)cout<<dp[i][t][j]<<" ";
//            cout<<endl;
        }

        for(int k = 0; k < 4; k++) a[k].clear();

        f(i, N);


    }

//    for(int i = 1; i <= N; i++) {
//        for(int j  =0; j <= N; j++) cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }

    long long ans = 0;
    for(int j = 0; j < fish[N-1].size(); j++) ans = max(ans, dp[N-1][2][j]);
    return ans;
}

Compilation message (stderr)

fish.cpp: In function 'void f(int, int)':
fish.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j = 1; j < fish[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~
fish.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = 1; j < fish[i-1].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:141:13: warning: unused variable 't' [-Wunused-variable]
  141 |     for(int t : fish[0]) for(int j = 0; j < 3; j++) dp[0][j].push_back(0);
      |             ^
fish.cpp:148:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int j = 0; j < fish[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:157:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             if(it1 < fish[i-1].size()) dp[i][1][j] = a[0][it1] - sum[i][it2];
      |                ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:180:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |                 if(it1 < fish[i-2].size()) dp[i][0][j] = max(dp[i][0][j], a[3][it1]);
      |                    ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:202:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for(int j = 0; j < fish[N-1].size(); j++) ans = max(ans, dp[N-1][2][j]);
      |                    ~~^~~~~~~~~~~~~~~~~~

• 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