oj.uz

Submission #1070789

# Submission time Handle Problem Language Result Execution time Memory
1070789 2024-08-22T18:32:29 Z beaconmc Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 286912 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

const ll maxn = 3005;


set<ll> heights[maxn];
vector<ll> realheights[maxn];

unordered_map<ll,ll> fish[maxn];
unordered_map<ll,ll> weights[maxn];

unordered_map<ll,ll> p[maxn];

vector<array<ll,2>>  dp[maxn];

unordered_map<ll,ll> pref[maxn][2];
unordered_map<ll,ll> pref2[maxn][2];
unordered_map<ll,ll> suff[maxn][2];


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    FOR(i,0,M){
        Y[i]++;
        fish[X[i]][Y[i]] = 1;
        weights[X[i]][Y[i]] = W[i];

        if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
        if (X[i] > 1) heights[X[i]-2].insert(Y[i]);
        heights[X[i]].insert(Y[i]);
        heights[X[i]+1].insert(Y[i]);
        heights[X[i]+2].insert(Y[i]);
    }
    FOR(i,0,maxn) heights[i].insert(0);

    FOR(i,0,maxn) heights[i].insert(maxn);

    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        for (auto j : heights[i]){
            if (j==0) continue;
            p[i][j] = p[i][prev] + weights[i][j];
            prev = j;
        }
    }
    FOR(i,0,maxn){
        for (auto k : heights[i]) realheights[i].push_back(k);
    }
    FOR(i,0,maxn){
        dp[i].resize(heights[i].size());
    }

    FOR(i,1,N+1){
        FOR(X,0,dp[i].size()){
            ll j = realheights[i][X];
            FOR(k,0,2){


                if (i<2) continue;
                ll temp = 0;
                ll add = 0;
                if (k==0){
                    if (X==dp[i].size()-1) continue;
                    ll up = *upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]);
                    ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                    temp = max(temp, suff[i-1][0][up] - p[i-1][down]);
                    temp = max(temp, suff[i-1][1][up] - p[i-1][down]);

                    // FOR(p,j+1,N+1){
                    //     if (fish[i-1][p]) add += weights[i-1][p];
                    //     temp = max(temp, dp[i-1][p][0] + add);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }else{
                    ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                    ll down2 = *(--upper_bound(realheights[i-2].begin(), realheights[i-2].end(), realheights[i][X]));

                    temp = max(temp, pref[i-1][0][down]);
                    temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);

                    // FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
                    // FOR(p,0,j+1){
                    //     if (fish[i-2][p]) add -= weights[i-2][p];
                    //     temp = max(temp, dp[i-1][p][0]);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }


                dp[i][X][k] = temp;
            }
        }
        ll sz = realheights[i].size();

        FOR(k,0,2){
            ll tempadd = 0;
            ll tempadd2 = 0;


            FOR(j,0,sz){
                tempadd += weights[i][realheights[i][j]];
                suff[i][k][realheights[i][j]] = dp[i][j][k]+tempadd;
            }

            FOR(j,0,sz){
                tempadd2 -= weights[i-1][realheights[i][j]];
                pref[i][k][realheights[i][j]] = dp[i][j][k] + tempadd2;
                pref2[i][k][realheights[i][j]] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][realheights[i][j]] = max(pref[i][k][realheights[i][j]], pref[i][k][prev]);
                pref2[i][k][realheights[i][j]] = max(pref2[i][k][realheights[i][j]], pref2[i][k][prev]);
                prev = realheights[i][j];
            }
            prev = realheights[i][sz-1];
            FORNEG(j,sz-2,-1){
                suff[i][k][realheights[i][j]] = max(suff[i][k][realheights[i][j]], suff[i][k][prev]);

                prev = realheights[i][j];
            }

        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << endl;

    }


    // cout << dp[3][2][0] << endl;



    ll ans = 0;

    FOR(i,0,N+1){
        FOR(j,0,dp[i].size()){
            ans = max(dp[i][j][0], ans);
            ans = max(dp[i][j][1], ans);
        }
    }
    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:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   65 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:65:9: note: in expansion of macro 'FOR'
   65 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:74:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:72:20: warning: unused variable 'add' [-Wunused-variable]
   72 |                 ll add = 0;
      |                    ^~~
fish.cpp:66:16: warning: unused variable 'j' [-Wunused-variable]
   66 |             ll j = realheights[i][X];
      |                ^
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  148 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:148:9: note: in expansion of macro 'FOR'
  148 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 175216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3416 KB Output is correct
2 Runtime error 593 ms 286912 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3676 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 3 ms 3420 KB Output is correct
5 Correct 3 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 4 ms 3932 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 4 ms 4188 KB Output is correct
12 Correct 6 ms 4700 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 5 ms 4532 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3676 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 3 ms 3420 KB Output is correct
5 Correct 3 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 4 ms 3932 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 4 ms 4188 KB Output is correct
12 Correct 6 ms 4700 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 5 ms 4532 KB Output is correct
15 Correct 6 ms 4440 KB Output is correct
16 Correct 8 ms 5208 KB Output is correct
17 Correct 108 ms 36180 KB Output is correct
18 Correct 84 ms 30288 KB Output is correct
19 Correct 118 ms 34132 KB Output is correct
20 Correct 81 ms 26960 KB Output is correct
21 Correct 76 ms 26196 KB Output is correct
22 Correct 180 ms 49588 KB Output is correct
23 Correct 51 ms 19804 KB Output is correct
24 Correct 107 ms 40532 KB Output is correct
25 Correct 7 ms 5208 KB Output is correct
26 Correct 37 ms 15708 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3420 KB Output is correct
2 Correct 4 ms 3676 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 3 ms 3420 KB Output is correct
5 Correct 3 ms 3420 KB Output is correct
6 Correct 4 ms 3420 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 4 ms 3932 KB Output is correct
10 Correct 7 ms 4700 KB Output is correct
11 Correct 4 ms 4188 KB Output is correct
12 Correct 6 ms 4700 KB Output is correct
13 Correct 3 ms 3676 KB Output is correct
14 Correct 5 ms 4532 KB Output is correct
15 Correct 6 ms 4440 KB Output is correct
16 Correct 8 ms 5208 KB Output is correct
17 Correct 108 ms 36180 KB Output is correct
18 Correct 84 ms 30288 KB Output is correct
19 Correct 118 ms 34132 KB Output is correct
20 Correct 81 ms 26960 KB Output is correct
21 Correct 76 ms 26196 KB Output is correct
22 Correct 180 ms 49588 KB Output is correct
23 Correct 51 ms 19804 KB Output is correct
24 Correct 107 ms 40532 KB Output is correct
25 Correct 7 ms 5208 KB Output is correct
26 Correct 37 ms 15708 KB Output is correct
27 Correct 29 ms 12120 KB Output is correct
28 Correct 652 ms 134740 KB Output is correct
29 Execution timed out 1035 ms 227184 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 175216 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -