Submission #831207

#	Time	Username	Problem	Language	Result	Execution time	Memory
831207		Wael	Catfish Farm (IOI22_fish)	C++17	84 / 100	1031 ms	163168 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int const Mx = 1e5 + 10;
int n , m , j;
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;

    for(int i = 0 ; i < m ; ++i) {
        ++X[i];
        ++Y[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];
    }

    for(int i = 1 ; i <= n + 1 ; ++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);
        }
    }

    long long MaxPref = 0 , MaxSuf = pref[2].back() , MaxDp = 0 , MaxAddDp = 0;
    for(int i = 2 ; i <= n ; ++i) {
        int Req = 0 , ReqNext = 0;
        for(int J = 0 ; J < possible[i].size() ; ++J) {
            j = possible[i][J];
            while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= j) ++Req;
            dp[0][i][J] = max(dp[0][i][J] , MaxPref + pref[i - 1][Req]);
            dp[1][i][J] = max(dp[1][i][J] , MaxSuf - pref[i][J]);
            if(i >= 3) {
               dp[0][i][J] = max(dp[0][i][J] , MaxDp + pref[i - 1][Req]);
               dp[0][i][J] = max(dp[0][i][J] , MaxAddDp - pref[i - 1][Req]);
            }
            ans = max(ans , dp[0][i][J]);
            ans = max(ans , dp[1][i][J]);
        }

        MaxPref = MaxSuf = MaxDp = MaxAddDp = 0;
        for(int J = 0 ; J < possible[i].size() ; ++J) {
            j = possible[i][J];
            while(ReqNext + 1 < possible[i + 1].size() && possible[i + 1][ReqNext + 1] <= j) ++ReqNext;
            MaxPref = max(MaxPref , dp[0][i][J] - pref[i][J]);
            MaxSuf = max(MaxSuf , max(dp[0][i][J] , dp[1][i][J]) + pref[i + 1][ReqNext]);
        }

        Req = 0;
        for(int J = 0 ; J < possible[i - 1].size() ; ++J) {
            j = possible[i - 1][J];
            while(Req + 1 < possible[i].size() && possible[i][Req + 1] <= j) ++Req;
            MaxDp = max(MaxDp , max(dp[0][i - 1][J] , dp[1][i - 1][J]));
            MaxAddDp = max(MaxAddDp , max(dp[0][i - 1][J] , dp[1][i - 1][J]) + pref[i][Req]);
        }
    }

    return ans;
}
/*
pref = max Dp - prefi
suf = max Dp - prefi + 1
Pref = max Dp
Suf = max Dp + prefi + 1
*/

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:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int J = 0 ; J < possible[i].size() ; ++J) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 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:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             while(ReqNext + 1 < possible[i + 1].size() && possible[i + 1][ReqNext + 1] <= j) ++ReqNext;
      |                   ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int J = 0 ; J < possible[i - 1].size() ; ++J) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             while(Req + 1 < possible[i].size() && possible[i][Req + 1] <= j) ++Req;
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~

• 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: 0 / 16