Submission #626306

#	Time	Username	Problem	Language	Result	Execution time	Memory
626306		jeroenodb	Catfish Farm (IOI22_fish)	C++17	9 / 100	159 ms	23396 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const ll oo = 1e18;
void cmax(ll& a, ll b) {a=max(a,b);}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    vvi ys(N+1);
    bool allEven=1;
    ll total=0;
    for(int i=0;i<M;++i) {
        if(X[i]%2!=0) allEven=0;
        Y[i]++,X[i]++;
        total+=W[i];
        ys[X[i]].push_back(i);
    }

    vector<vector<ll>> pref(N+1,{0});
    {
    int x=0;
    for(auto& v : ys) {
        sort(all(v),[&](int i, int j) {return Y[i]<Y[j];});
        for(auto& id : v) {
            pref[x].push_back(W[id]);
            id = Y[id];
        }
        pref[x].push_back(0);
        v.insert(v.begin(),0);
        v.push_back(N+1);
        partial_sum(all(pref[x]),pref[x].begin());
        assert(pref[x].size()==v.size());
        x++;
        
    }
    }
    // dynamic programming
    // DP[column][y-pos][state] 
    // state {0: rising, 1: falling}
    // transition going up: 
    array<vector<ll>,2> dp = {vector<ll>{0LL,-oo},{-oo,-oo}};
    ll top = -oo;
    auto getS = [&](int x, int y) {
        auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1LL);
        return pref[x][i];
    };
    for(int x=1;x<=N;++x) {
        int k = ys[x].size();
        array<vector<ll>,2> ndp = {vector<ll>(k,-oo),vector<ll>(k,-oo)};
        for(auto& v : dp[1]) {
            cmax(dp[0][0],v);
        }
        // falling to falling
        {
        int j = ys[x-1].size()-1;
        ll best = -oo;
        for(int i=k-1;i>=0;--i) {
            while(j>=0 and ys[x-1][j]>=ys[x][i]) {
                cmax(best,dp[1][j]);
                --j;
            }
            cmax(ndp[1][i], best-getS(x-1,ys[x][i]) + pref[x][i]);
        }
        }
        // rising to rising
        {
        int j = 0;
        ll best = -oo;
        for(int i=0;i<k;++i) {
            while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
                cmax(best,dp[0][j]-getS(x,ys[x-1][j]));
                ++j;
            }
            cmax(ndp[0][i], best + pref[x][i]);
        }
        }
        // falling to rising, far apart
        {
        ll best = *max_element(all(dp[1]));
        for(int i=0;i<k;++i) 
            cmax(ndp[0][i],best+pref[x][i]);
        }
        // falling to rising, case 2
        {
        int j = 0;
        ll best = -oo;
        for(int i=0;i<k;++i) {
            while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
                cmax(best,dp[1][j]-getS(x,ys[x-1][j])-pref[x-1][j]);
                ++j;
            }
            cmax(ndp[0][i], best + pref[x][i] + getS(x-1, ys[x][i]));
        }

        }
        // top to falling
        for(int i=0;i<k;++i) {
            cmax(ndp[1][i],pref[x][i]+top);
        }
        // rising to top
        cmax(top,*max_element(all(dp[0])));

        swap(dp,ndp);
    }
    // falling or top
    auto ans = max(top,*max_element(all(dp[1])));;
    assert(ans<=total);
    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:17:10: warning: variable 'allEven' set but not used [-Wunused-but-set-variable]
   17 |     bool allEven=1;
      |          ^~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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