Submission #1051595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051595		Itamar	Catfish Farm (IOI22_fish)	C++17	100 / 100	476 ms	163344 KiB

fish

using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#include<map>
#define pi pair<int,int>
#include <algorithm>
#include<unordered_map>
#define map unordered_map
ll max_weights(int N, int M, vi X, vi Y, vi W){
    for(int i = 0; i < M; i++)X[i]++,Y[i]++;
    vector<vi> fish(N+2);
    vector<map<int,int>> w(N+2);
    vector<map<int,ll>> s(N+2);
    vector<map<int,ll>> dp(N+2);
    vector<map<int,ll>> pref(N+2); // maximum (prefix - prefix_sum), notice initialization
    ll ans = 0;
    ll su=0;
    for(int i = 0; i <= N+1; i++){
        fish[i].push_back(0);fish[i].push_back(N+2);
    }
    for(int i = 0; i < M; i++){
        fish[X[i]].push_back(Y[i]);
        w[X[i]][Y[i]]=W[i];
    }
    for(int i = 0; i < N+2; i++)sort(fish[i].begin(),fish[i].end());
    for(int i = 0; i < N+2; i++){
        for(int j = 1; j < fish[i].size(); j++){
            s[i][fish[i][j]] = s[i][fish[i][j-1]]+w[i][fish[i][j-1]];
        }
    }
    for(int i = 1; i < N+1; i++){
        int dub = 0;
        for(int y : fish[i]){
            dp[i][y] = max(dp[i][y], su-s[i][y]);
            if(y){int predown = *--upper_bound(fish[i-1].begin(),fish[i-1].end(),y-1); // maybe y-1
            dp[i][y]=max(dp[i][y], pref[i-1][predown]+s[i-1][predown]+w[i-1][predown]);
            }
            //ans = max(ans,dp[i][y]);
        }
        int maxi = 0;
        int it = 0;
        pref[i][0] = ans;
        for(int y : fish[i])ans = max(ans,dp[i][y]);
         for(int j = 1; j < fish[i].size(); j++){
            int y = fish[i][j], prey=fish[i][j-1];
            pref[i][y] = pref[i][prey];
            int predown = *--upper_bound(fish[i-1].begin(),fish[i-1].end(),y-1); // maybe y-1
            pref[i][y]=max(pref[i][y], pref[i-1][predown]+s[i-1][predown]-s[i][y]+w[i-1][predown]);
        }
        su= s[i+1][N+2] + dp[i][N+2];
        for(int j = fish[i].size()-2; j>=0; j--){
            int y = fish[i][j],yaf = fish[i][j+1];
            int predown = *upper_bound(fish[i+1].begin(),fish[i+1].end(),y-1);
            su = max(su, dp[i][y] + s[i+1][predown]);
        }
    }
    return ans;
}

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:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int j = 1; j < fish[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
fish.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |          for(int j = 1; j < fish[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:54:32: warning: unused variable 'yaf' [-Wunused-variable]
   54 |             int y = fish[i][j],yaf = fish[i][j+1];
      |                                ^~~
fish.cpp:34:13: warning: unused variable 'dub' [-Wunused-variable]
   34 |         int dub = 0;
      |             ^~~
fish.cpp:42:13: warning: unused variable 'maxi' [-Wunused-variable]
   42 |         int maxi = 0;
      |             ^~~~
fish.cpp:43:13: warning: unused variable 'it' [-Wunused-variable]
   43 |         int it = 0;
      |             ^~

• 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