oj.uz

Submission #628868

# Submission time Handle Problem Language Result Execution time Memory
628868 2022-08-13T18:45:06 Z dacin21 Catfish Farm (IOI22_fish) C++17
12 / 100
 212 ms 52548 KB 
#include "fish.h"

#include <bits/stdc++.h>

using namespace std;
using ll = int64_t;

template<typename S, typename T>
void xmax(S&a, T const&b){
    if(b>a) a = b;
}

struct Fish{
    int y;
    ll w;
    ll left = 0, middle = 0, right = 0;
};
struct DP{
    vector<ll> up, down;
    ll zero_with = 0, zero_without = 0;
    ll next_zero_with = 0, next_zero_without = 0;
};

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<Fish> > ev(N+2);
    for(int i=0; i<M; ++i){
        ev[X[i]+1].push_back(Fish{Y[i], W[i]});
        ev[X[i]+1].push_back(Fish{Y[i]+1, 0});
    }
    for(auto &e : ev) {
        e.push_back(Fish{-1, 0});
        e.push_back(Fish{N+1, 0});
        sort(e.begin(), e.end(), [&](auto const&a, auto const&b){ return a.y < b.y; });
        for(int i=1; i<(int)e.size(); ++i){
            e[i].middle = e[i-1].middle + e[i-1].w;
        }
    }
    for(int x=0; x<=N; ++x){
        auto &L = ev[x], &R = ev[x+1];
        int i = (int)L.size()-1, j = (int)R.size()-1;
        while(i >= 0 && j >= 0){
            auto &l = L[i], &r = R[j];
            if(l.y < r.y){
                r.left = l.middle;
                --j;
            } else if(l.y > r.y){
                l.right = r.middle;
                --i;
            } else {
                l.right = r.middle;
                r.left = l.middle;
                --i; --j;
            }
        }
    }
    DP prev;
    prev.up.assign(2, 0);
    prev.down.assign(2, 0);
    for(int x=1; x<=N+1; ++x){
        auto &you = ev[x-1];
        auto &me = ev[x];
        /* compute up: For each height
         *  - find best pred
         *  - add left
         *  - subtract me (due to next up)
         *  - check transform into down
         *
         * compute down: For each height
         *  - find best pred (or cur.up)
         *  - add right
         *  - subtract me (due to prev down)
         *  - check transform to zero.
         *
         */
        DP cur;
        cur.up.assign(me.size(), 0);
        cur.down.assign(me.size(), 0);
        /// compute up
        {
            int i = (int)you.size()-1, j = (int)me.size()-1;
            while(i >= 0 && j >= 0){
                if(you[i].y > me[j].y) --i;
                else {
                    cur.up[j] = prev.up[i];
                    --j;
                }
            }
        }
        // add left - middle
        // also consider the zero start
        for(int i=0; i<(int)me.size(); ++i){
            xmax(cur.up[i], prev.zero_without);
            cur.up[i] += me[i].left;
            xmax(cur.up[i], prev.zero_with);
            cur.up[i] -= me[i].middle;
        }
        /// update zeros
        cur.zero_with = prev.next_zero_with;
        cur.zero_without = prev.next_zero_without;
        /// compute down
        {
            // find best pred
            int i = 0, j = 0;
            while(i < (int)you.size() && j < (int)me.size()){
                if(you[i].y < me[j].y) ++i;
                else {
                    cur.down[j] = max(prev.down[i], cur.up[j] + 2*me[j].middle);
                    ++j;
                }
            }
        }
        // add right - middle
        // consider creating zeros
        for(int i = (int)me.size()-1; i > 0; --i){
            cur.down[i] -= me[i].middle;
            xmax(cur.next_zero_without, cur.down[i]);
            cur.down[i] += me[i].right;
            xmax(cur.next_zero_with, cur.down[i]);
        }
        /*cerr << "at: " << x << "\n";
        for(int i=0; i<(int)me.size(); ++i){
            auto &e = me[i];
            cerr << e.y << " " << e.w << " : " << e.left << " / " << e.middle << " / " << e.right << " : ";
            cerr << cur.up[i] << " | " << cur.down[i] << "\n";
        }*/
        /// turn values into prefix / suffic maxima
        // move up
        for(int i=1; i<(int)me.size(); ++i){
            xmax(cur.up[i], cur.up[i-1]);
        }
        // move down
        for(int i = (int)me.size()-1; i > 0; --i){
            xmax(cur.down[i-1], cur.down[i]);
        }
        prev = move(cur);
    }
    return max(prev.zero_with, prev.up[0]);
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 21560 KB Output is correct
2 Correct 80 ms 25260 KB Output is correct
3 Correct 23 ms 11988 KB Output is correct
4 Correct 24 ms 11988 KB Output is correct
5 Correct 207 ms 45340 KB Output is correct
6 Correct 212 ms 52548 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11968 KB Output is correct
2 Correct 25 ms 11988 KB Output is correct
3 Correct 50 ms 16832 KB Output is correct
4 Correct 45 ms 15800 KB Output is correct
5 Correct 81 ms 24088 KB Output is correct
6 Correct 74 ms 24012 KB Output is correct
7 Correct 83 ms 24072 KB Output is correct
8 Correct 81 ms 24016 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11968 KB Output is correct
2 Correct 25 ms 11988 KB Output is correct
3 Correct 50 ms 16832 KB Output is correct
4 Correct 45 ms 15800 KB Output is correct
5 Correct 81 ms 24088 KB Output is correct
6 Correct 74 ms 24012 KB Output is correct
7 Correct 83 ms 24072 KB Output is correct
8 Correct 81 ms 24016 KB Output is correct
9 Correct 87 ms 24088 KB Output is correct
10 Incorrect 78 ms 21832 KB 1st lines differ - on the 1st token, expected: '36454348383152', found: '36858053676967'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 21560 KB Output is correct
2 Correct 80 ms 25260 KB Output is correct
3 Correct 23 ms 11988 KB Output is correct
4 Correct 24 ms 11988 KB Output is correct
5 Correct 207 ms 45340 KB Output is correct
6 Correct 212 ms 52548 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 115 ms 32500 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40604922198817'
9 Halted 0 ms 0 KB -