Submission #626845

#	Time	Username	Problem	Language	Result	Execution time	Memory
626845		welleyth	Catfish Farm (IOI22_fish)	C++17	37 / 100	635 ms	84428 KiB

fish

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

constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)2e18 + 10;

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")

int cnt[NN];
vector<pair<int,long long>> val[NN];
vector<int> possibleLen[NN];

long long getSum(int x,int r){
    if(val[x].empty())
        return 0;
    if(val[x][0].first >= r)
        return 0;
    return (upper_bound(val[x].begin(),val[x].end(),make_pair(r-1,INF))-1)->second;
}

mt19937 rnd(time(nullptr));

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    long long dp[2][333][333];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 333; j++){
            for(int t = 0; t < 333; t++){
                dp[i][j][t] = 0;
            }
        }
    }
    set<int> st[N+22];
    for(int i = 0; i < M; i++){
//        g[X[i]+2][Y[i]] = W[i];
        val[X[i]+2].push_back(make_pair(Y[i],W[i]));
        for(int j = max(2,X[i]+1); j <= X[i]+3; j++){
            st[j].insert(Y[i]+1);
        }
    }

    for(int i = 0; i < N+2; i++){
        st[i].insert(0);
        st[i].insert(N);
        possibleLen[i] = vector<int>(st[i].begin(),st[i].end());
        sort(val[i].begin(),val[i].end());
        for(int j = 1; j < val[i].size(); j++){
            val[i][j].second += val[i][j-1].second;
        }
    }

//    cerr << getSum(2,3) << "\n";
//    return 0;

    long long ans = 0;

    for(int i = 2; i < N+2; i++){
        int pr[2];
        for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                int lcur = possibleLen[i][cur];
                int l1 = possibleLen[i-2][pr[1]];
                pr[0] = lower_bound(possibleLen[i-1].begin(),possibleLen[i-1].end(),min(l1,lcur)-1) - possibleLen[i-1].begin();
                pr[0] = max(0,pr[0]-10);
                pr[0] = min((int)possibleLen[i-1].size()-1,pr[0]);
                for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
                    int l0 = possibleLen[i-1][pr[0]];
                    if(lcur <= l0){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,lcur));
                    } else if(lcur <= l1){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0));
                    } else {
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0)
                                            + max(0ll,getSum(i-1,lcur)-getSum(i-1,l0)) - max(0ll,getSum(i-1,l1)-getSum(i-1,l0)));
                    }
                    ans = max(ans,dp[1][pr[0]][cur]);
//                    cerr << i << " " << l1 << " " << l0 << " " << lcur << " " << dp[1][pr[0]][cur] << "\n";
//                    if(dp[0][pr[0]][cur] == 0)
//                        continue;
                }
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
                dp[0][pr[1]][pr[0]] = 0;
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[0][pr[0]][cur] = dp[1][pr[0]][cur];
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[1][pr[0]][cur] = 0;
            }
        }
    }
//    for(int i = 0; i < N+2; i++){
//        for(int j = 0; j < 10; j++){
//            for(int t = 0; t < 10; t++){
//                ans = max(ans,dp[i][j][t]);
//            }
//        }
//    }

    return ans;
}
/**
10000 2
0 0 1
0 1 1

5 4
0 2 5
1 1 2
4 4 1
3 3 3


**/

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j = 1; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:62:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:68:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:85:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:86:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:90:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:91:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:95:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:96:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~

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