Submission #831140

#	Time	Username	Problem	Language	Result	Execution time	Memory
831140		Wael	Catfish Farm (IOI22_fish)	C++17	67 / 100	1080 ms	100044 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int const Mx = 1e5 + 10;
long long n , m;
map<int , int>cost[Mx] , vis[Mx];
vector<int>possible[Mx];
vector<long long>pref[Mx] , dp[3][Mx];

long long max_weights(int N, int M , vector<int> X, vector<int> Y, vector<int> W) {
    m = M , n = N;
    long long ans = 0 , Sum = 0;
    int MaxX = 0 , Even = 1;

    for(int i = 0 ; i < m ; ++i) {
        ++X[i];
        ++Y[i];
        Sum += W[i];
        if(X[i] % 2 == 0) Even = 0;
        MaxX = max(MaxX , X[i]);
        if(vis[X[i] - 1][Y[i]] == 0) possible[X[i] - 1].push_back(Y[i]);
        if(vis[X[i] + 1][Y[i]] == 0) possible[X[i] + 1].push_back(Y[i]);
        if(vis[X[i]][Y[i]] == 0) possible[X[i]].push_back(Y[i]);
        vis[X[i] - 1][Y[i]] = 1;
        vis[X[i] + 1][Y[i]] = 1;
        vis[X[i]][Y[i]] = 1;
        cost[X[i]][Y[i]] = W[i];
    }

    if(Even) return Sum;
    for(int i = 1 ; i <= n ; ++i) {
        possible[i].push_back(0);
        sort(possible[i].begin() , possible[i].end());
        for(auto j : possible[i]) {
            long long cur = 0;
            if(pref[i].size()) cur = pref[i].back();
            cur += cost[i][j];
            pref[i].push_back(cur);
            dp[0][i].push_back(0);
            dp[1][i].push_back(0);
        }
    }

    if(MaxX <= 2) {
        if(n == 2) return max(pref[1].back() , pref[2].back());
        long long sum = pref[2].back();
        int Req = 0;
        for(int j = 0 ; j < possible[1].size() ; ++j) {
            while(Req + 1 < possible[2].size() && possible[2][Req + 1] <= possible[1][j]) ++Req;
            ans = max(ans , sum - pref[2][Req] + pref[1][j]);
        }
        return ans;
    }

    for(int i = 2 ; i <= n ; ++i) {
        for(int J = 0 ; J < possible[i].size() ; ++J) {
            int j = possible[i][J];
            int Req1 = 0 , Req2 = 0;
            while(Req1 + 1 < possible[i - 1].size() && possible[i - 1][Req1 + 1] <= j) ++Req1;
            for(int K = 0 ; K <  possible[i - 1].size() ; ++K) {
                int k = possible[i - 1][K];
                while(Req2 + 1 < possible[i].size() && possible[i][Req2 + 1] <= k) ++Req2;
                if(k <= j) dp[0][i][J] = max(dp[0][i][J] , dp[0][i - 1][K] + pref[i - 1][Req1] - pref[i - 1][K]);
                else dp[1][i][J] = max(dp[1][i][J] , max(dp[0][i - 1][K] , dp[1][i - 1][K]) + pref[i][Req2] - pref[i][J]);
            }
            if(i >= 3) {
                int Req = 0;
                for(int K = 0 ; K < possible[i - 2].size() ; ++K) {
                    int k = possible[i - 2][K];
                    while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= max(j , k)) ++Req;
                    dp[0][i][J] = max(dp[0][i][J] , max(dp[0][i - 2][K] , dp[1][i - 2][K]) + pref[i - 1][Req]);
                }
            }
            ans = max(ans , dp[0][i][J]);
            ans = max(ans , dp[1][i][J]);
        }
    }

    return ans;
}
/*
3 4
1 1 5
1 2 10
2 1 5
3 1 5
*/

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:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 0 ; j < possible[1].size() ; ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while(Req + 1 < possible[2].size() && possible[2][Req + 1] <= possible[1][j]) ++Req;
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int J = 0 ; J < possible[i].size() ; ++J) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:59:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             while(Req1 + 1 < possible[i - 1].size() && possible[i - 1][Req1 + 1] <= j) ++Req1;
      |                   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:60:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for(int K = 0 ; K <  possible[i - 1].size() ; ++K) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:62:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 while(Req2 + 1 < possible[i].size() && possible[i][Req2 + 1] <= k) ++Req2;
      |                       ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:68:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(int K = 0 ; K < possible[i - 2].size() ; ++K) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:70:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                     while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= max(j , k)) ++Req;
      |                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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