oj.uz

Submission #1019877

# Submission time Handle Problem Language Result Execution time Memory
1019877 2024-07-11T10:10:38 Z Gray Catfish Farm (IOI22_fish) C++17
12 / 100
 154 ms 35668 KB 
#include "fish.h"
 
#include <algorithm>
#include <cassert>
#include <deque>
#include <iostream>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
 
 
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    ll n=N, m=M;
    vector a(N, vector<pair<ll, ll>>());
    vector dp(N, vector<pair<ll, ll>>());
    for (ll i=0; i<m; i++){
        a[X[i]].push_back({W[i], Y[i]});
        dp[X[i]].push_back({0, 0});
    }
    for (ll i=0; i<n; i++){
        sort(a[i].begin(), a[i].end());
        dp[i].push_back({0, 0});
    }
    for (ll i=1; i<N; i++){
        // cout << i << ": " << endl;
        deque<pair<ll, ll>> bestU;
        pair<ll, ll> mx = {-1, -1};
        ll sum=0, rsum=0;
        for (ll j=0; j<(ll)a[i].size(); j++) rsum+=a[i][j].ff;
        sum=rsum;
        ll pi=a[i].size()-1;
        for (ll j=a[i-1].size(); j>=0; j--){
            while (j<(ll)a[i-1].size() and pi>=0 and a[i-1][j].ss-1<a[i][pi].ss) sum-=a[i][pi--].ff;
            if (max(dp[i-1][j].ff, dp[i-1][j].ss)+sum>mx.ff){
                mx = {max(dp[i-1][j].ff, dp[i-1][j].ss)+sum, (j==(ll)a[i-1].size())?n:a[i-1][j].ss-1};
                bestU.push_back(mx);
                // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
        }
        sum=0;
        for (ll j=0; j<=(ll)a[i].size(); j++){
            while (!bestU.empty() and bestU.back().ss<(j==(ll)a[i].size()?n:a[i][j].ss-1)) {
                // cout << "Remove: " << bestU.back().ff << " " << bestU.back().ss << " at " << j << endl;
                bestU.pop_back();
            }
            // cout << i << "-" << j << endl;
            dp[i][j].ss=(bestU.empty()?0:bestU.back().ff)-sum;
            if (j<(ll)a[i].size()) sum+=a[i][j].ff;
            // cout << i << "-" << j << endl;
        }
        if (i>1){ //-Change-
            // cout << i << ": ";
            pair<ll, ll> best = {-1, -1};
            for (ll j=0; j<=(ll)a[i-2].size(); j++){
                best=max(best, {max(dp[i-2][j].ff, dp[i-2][j].ss), (j==(ll)(a[i-2].size())?n:a[i-2][j].ss-1)});
            }
            ll osum=0;
            for (ll j=0; j<(ll)a[i-1].size() and a[i-1][j].ss<=best.ss; j++){
                osum+=a[i-1][j].ff;
            }
            // cout << osum << " -> ";
            sum=0;
            pi=0;
            for (ll j=0; j<=(ll)a[i].size(); j++){
                while (pi<(ll)a[i-1].size() and a[i-1][pi].ss<=(j==(ll)(a[i].size())?n:a[i][j].ss-1)) sum+=a[i-1][pi++].ff;
                dp[i][j].ff=best.ff+max(sum, osum);
            }
        }
        assert(bestU.size()<=1);
        while (!bestU.empty()) bestU.pop_back();
        mx = {-1, -1};
        sum=rsum=0;
        for (ll j=0; j<(ll)a[i-1].size(); j++) rsum+=a[i-1][j].ff;
        for (ll j=0; j<=(ll)a[i-1].size(); j++){
            if (rsum-sum+dp[i-1][j].ff>mx.ff){
                mx = {rsum-sum+dp[i-1][j].ff, (j==(ll)a[i-1].size()?n:a[i-1][j].ss-1)};
                bestU.push_back(mx);
                // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
            if (j<(ll)a[i-1].size()) sum+=a[i-1][j].ff;
        }
        sum=0;
        pi=(ll)a[i-1].size()-1;
        for (ll j=(ll)(a[i].size()); j>=0; j--){
            while (pi>=0 and a[i-1][pi].ss>(j==(ll)(a[i].size())?n+1:a[i][j].ss-1)) sum+=a[i-1][pi--].ff;
            while (!bestU.empty() and bestU.back().ss>(j==(ll)(a[i].size())?n+1:a[i][j].ss-1)) {
                // cout << "Remove: " << bestU.back().ff << " " << bestU.back().ss << " at " << j << endl;
                bestU.pop_back();
            }
            // cout << i << "-" << j << endl;
            dp[i][j].ff=max(dp[i][j].ff, (bestU.empty()?0:bestU.back().ff)-sum);
        }
    }
    // for (ll i=0; i<n; i++){
    //     // for (ll j=0; j<dp[i].size(); j++) cout << dp[i][j].ff << " ";
    //     // cout << ln;
    // }
    // for (ll i=0; i<n; i++){
    //     // for (ll j=0; j<dp[i].size(); j++) cout << dp[i][j].ss << " ";
    //     // cout << ln;
    // }
    // Thing to lookup -> the fact that dp[i][j] is column up to height[i][j]-1;
    ll res=0;
    for (ll i=0; i<=(ll)a[n-1].size(); i++){
        res=max(res, max(dp[n-1][i].ff,dp[n-1][i].ss));
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13236 KB Output is correct
2 Correct 39 ms 15288 KB Output is correct
3 Correct 11 ms 8276 KB Output is correct
4 Correct 11 ms 8028 KB Output is correct
5 Correct 109 ms 32468 KB Output is correct
6 Correct 154 ms 35668 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 57 ms 19084 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8028 KB Output is correct
2 Correct 11 ms 8276 KB Output is correct
3 Correct 36 ms 12624 KB Output is correct
4 Correct 24 ms 11432 KB Output is correct
5 Correct 57 ms 20052 KB Output is correct
6 Correct 52 ms 19284 KB Output is correct
7 Correct 55 ms 19796 KB Output is correct
8 Correct 52 ms 19768 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218899290972'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218899290972'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '218899290972'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8028 KB Output is correct
2 Correct 11 ms 8276 KB Output is correct
3 Correct 36 ms 12624 KB Output is correct
4 Correct 24 ms 11432 KB Output is correct
5 Correct 57 ms 20052 KB Output is correct
6 Correct 52 ms 19284 KB Output is correct
7 Correct 55 ms 19796 KB Output is correct
8 Correct 52 ms 19768 KB Output is correct
9 Correct 50 ms 19536 KB Output is correct
10 Incorrect 48 ms 15180 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '37002306348565'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13236 KB Output is correct
2 Correct 39 ms 15288 KB Output is correct
3 Correct 11 ms 8276 KB Output is correct
4 Correct 11 ms 8028 KB Output is correct
5 Correct 109 ms 32468 KB Output is correct
6 Correct 154 ms 35668 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 57 ms 19084 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
9 Halted 0 ms 0 KB -