oj.uz

Submission #1019673

# Submission time Handle Problem Language Result Execution time Memory
1019673 2024-07-11T07:17:26 Z Gray Catfish Farm (IOI22_fish) C++17
0 / 100
 908 ms 2097152 KB 
#include "fish.h"

#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<ll>(N));
    for (ll i=0; i<m; i++){
        a[X[i]][Y[i]]+=W[i];
    }
    vector dp(N, vector<pair<ll, ll>>(N+1));
    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<N; j++) rsum+=a[i][j];
        sum=rsum;
        for (ll j=N; j>=0; j--){
            if (j<N) sum-=a[i][j];
            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};
                bestU.push_back(mx);
                // cout << "Add: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
        }
        sum=0;
        for (ll j=0; j<=N; j++){
            if (j) sum+=a[i][j-1];
            if (bestU.back().ss<j) {
                bestU.pop_back();
                // cout << "Remove: " << mx.ff << " " << mx.ss << " at " << j << endl;
            }
            dp[i][j].ss=bestU.back().ff-sum;
        }
        if (i>1){ //-Change-
            // cout << i << ": ";
            pair<ll, ll> best = {-1, -1};
            for (ll j=0; j<N+1; j++){
                best=max(best, {max(dp[i-2][j].ff, dp[i-2][j].ss), j});
            }
            ll osum=0;
            for (ll j=0; j<best.ss; j++){
                osum+=a[i-1][j];
            }
            // cout << osum << " -> ";
            sum=0;
            for (ll j=0; j<=n; j++){
                if (j) sum+=a[i-1][j-1];
                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<N; j++) rsum+=a[i-1][j];
        for (ll j=0; j<=N; j++){
            if (j) sum+=a[i-1][j-1];
            if (rsum-sum+dp[i-1][j].ff>mx.ff){
                mx = {rsum-sum+dp[i-1][j].ff, j};
                bestU.push_back(mx);
            }
        }
        sum=0;
        for (ll j=N; j>=0; j--){
            if (j<N) sum+=a[i-1][j];
            if (bestU.back().ss>j) bestU.pop_back();
            dp[i][j].ff=max(dp[i][j].ff, bestU.back().ff-sum);
        }
    }
    for (ll i=N; i>=0; i--){
        for (ll j=0; j<N; j++) cout << dp[j][i].ff << " ";
        cout << endl;
    }
    for (ll i=N; i>=0; i--){
        for (ll j=0; j<N; j++) cout << dp[j][i].ss << " ";
        cout << endl;
    }
    ll res=0;
    for (ll i=0; i<=n; i++){
        res=max(res, max(dp[n-1][i].ff,dp[n-1][i].ss));
    }
    return res;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 908 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 859 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Possible tampering with the output
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 859 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 908 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -