Submission #852713

#	Time	Username	Problem	Language	Result	Execution time	Memory
852713		abcvuitunggio	Catfish Farm (IOI22_fish)	C++17	3 / 100	447 ms	180844 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define MX mx[i][idx][b]
#define int long long
using namespace std;
const int INF=1e18;
vector <int> v[100001];
vector <pair <int, int>> s[100001],mx[100002][4][2];
int n,m;
int x,y,res;
void update(int pos, int val, int i, int idx){
    mx[pos][idx][0].push_back({i,val});
    mx[pos][idx][1].push_back({n-i+1,val});
}
int get(int pos, int i, int idx, int b){
    if (b)
        pos=n-pos+1;
    int p=upper_bound(MX.begin(),MX.end(),make_pair(pos,INF))-MX.begin()-1;
    return (p<0?-INF:MX[p].second);
}
int sum(int i, int j){
    if (i<0)
        return 0;
    return s[i][upper_bound(s[i].begin(),s[i].end(),make_pair(j,INF))-s[i].begin()-1].second;
}
int max_weights(int32_t N, int32_t M, vector <int32_t> X, vector <int32_t> Y, vector <int32_t> W){
    n=N;
    for (int i=0;i<M;i++){
        s[X[i]].push_back({Y[i],W[i]});
        if (X[i])
            v[X[i]-1].push_back(Y[i]);
        if (X[i]<N-1)
            v[X[i]+1].push_back(Y[i]);
    }
    for (int i=0;i<n;i++){
        v[i].push_back(-1);
        sort(v[i].begin(),v[i].end());
        v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
        s[i].push_back({-1,0});
        sort(s[i].begin(),s[i].end());
        for (int j=1;j<s[i].size();j++)
            s[i][j].second+=s[i][j-1].second;
    }
    for (int i:v[n-1]){
        update(n,0,i,0);
        update(n,0,i,1);
        update(n,-sum(n-1,i),i,2);
        update(n,sum(n-2,i),i,3);
    }
    for (int i=n-1;i;i--){
        for (int j:v[i-1]){
            x=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),max(get(j,i+1,0,1),get(j,i+1,1,1)));
            y=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),get(j,i+1,3,1)-sum(i-1,j));
            update(i,x,i,0);
            update(i,y,i,1);
            update(i,x-sum(i-1,j),i,2);
            update(i,max(x,y)+sum(i-2,j),i,3);
        }
        for (int j=0;j<4;j++){
            reverse(mx[i][j][1].begin(),mx[i][j][1].end());
            for (int k=0;k<2;k++)
                for (int l=1;l<mx[i][j][k].size();l++)
                    mx[i][j][k][l].second=max(mx[i][j][k][l].second,mx[i][j][k][l-1].second);
        }
    }
    return max(get(0,1,0,1),get(0,1,1,1));
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j=1;j<s[i].size();j++)
      |                      ~^~~~~~~~~~~~
fish.cpp:62:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for (int l=1;l<mx[i][j][k].size();l++)
      |                              ~^~~~~~~~~~~~~~~~~~~

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