oj.uz

Submission #626293

# Submission time Handle Problem Language Result Execution time Memory
626293 2022-08-11T10:59:59 Z jeroenodb Catfish Farm (IOI22_fish) C++17
9 / 100
 176 ms 24844 KB 
#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];
        }
        v.insert(v.begin(),0);
        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}};
    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)};
        // 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, case 1
        {
        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, spaced one apart. 
        {
        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]-pref[x][i]-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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 14608 KB Output is correct
2 Correct 65 ms 17808 KB Output is correct
3 Correct 19 ms 11140 KB Output is correct
4 Correct 20 ms 11272 KB Output is correct
5 Correct 166 ms 24844 KB Output is correct
6 Correct 176 ms 24128 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 100 ms 18764 KB Output is correct
3 Correct 115 ms 22968 KB Output is correct
4 Correct 50 ms 15144 KB Output is correct
5 Correct 60 ms 17284 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 19 ms 11220 KB Output is correct
11 Correct 20 ms 11272 KB Output is correct
12 Correct 53 ms 15036 KB Output is correct
13 Correct 61 ms 17272 KB Output is correct
14 Correct 50 ms 15072 KB Output is correct
15 Correct 80 ms 16736 KB Output is correct
16 Correct 58 ms 15092 KB Output is correct
17 Correct 56 ms 16756 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11220 KB Output is correct
2 Correct 21 ms 11220 KB Output is correct
3 Incorrect 40 ms 11580 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '23240317856269'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 216 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: '242970055215'
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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 216 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: '242970055215'
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 304 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 216 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: '242970055215'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11220 KB Output is correct
2 Correct 21 ms 11220 KB Output is correct
3 Incorrect 40 ms 11580 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '23240317856269'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 14608 KB Output is correct
2 Correct 65 ms 17808 KB Output is correct
3 Correct 19 ms 11140 KB Output is correct
4 Correct 20 ms 11272 KB Output is correct
5 Correct 166 ms 24844 KB Output is correct
6 Correct 176 ms 24128 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 100 ms 18764 KB Output is correct
9 Correct 115 ms 22968 KB Output is correct
10 Correct 50 ms 15144 KB Output is correct
11 Correct 60 ms 17284 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 19 ms 11220 KB Output is correct
17 Correct 20 ms 11272 KB Output is correct
18 Correct 53 ms 15036 KB Output is correct
19 Correct 61 ms 17272 KB Output is correct
20 Correct 50 ms 15072 KB Output is correct
21 Correct 80 ms 16736 KB Output is correct
22 Correct 58 ms 15092 KB Output is correct
23 Correct 56 ms 16756 KB Output is correct
24 Correct 20 ms 11220 KB Output is correct
25 Correct 21 ms 11220 KB Output is correct
26 Incorrect 40 ms 11580 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '23240317856269'
27 Halted 0 ms 0 KB -