oj.uz

Submission #1070912

# Submission time Handle Problem Language Result Execution time Memory
1070912 2024-08-22T20:42:51 Z beaconmc Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 243180 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 = 100005;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

 
 
unordered_set<ll> heights[maxn];
basic_string<ll> realheights[maxn];
 
 
gp_hash_table<ll, ll> weights;
 
basic_string<ll> p[maxn];
 
basic_string<array<ll,2>>  dp[maxn];
 
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<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]++;
        weights[X[i]*(ll)100000000+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){
        FOR(k,0,2){
            pref[i][k].resize(heights[i].size());
            pref2[i][k].resize(heights[i].size());
            suff[i][k].resize(heights[i].size());
        }
        p[i].resize(heights[i].size());
        dp[i].resize(heights[i].size());
    }
    FOR(i,0,maxn){
        for (auto k : heights[i]) realheights[i].push_back(k);
        sort(realheights[i].begin(), realheights[i].end());
    }
 
 
 
    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        FOR(j,1,heights[i].size()){
            p[i][j] = p[i][j-1] + weights[i*(ll)100000000+realheights[i][j]];
        }
    }
 
 
 
    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 down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
 
                    temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
                    temp = max(temp, suff[i-1][1][down] - 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(), j) - realheights[i-1].begin() - 1;
                    ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
 
 
                    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*(ll)100000000+realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[(i-1)*(ll)100000000+realheights[i][j]];
                pref[i][k][j] = dp[i][j][k] + tempadd2;
                pref2[i][k][j] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
                pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
 
            }
 
            FORNEG(j,sz-2,-1){
                suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
 
 
            }
 
        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << 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::unordered_set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   70 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:70:9: note: in expansion of macro 'FOR'
   70 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:69:12: warning: unused variable 'prev' [-Wunused-variable]
   69 |         ll prev = 0;
      |            ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<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++)
......
   79 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:79:9: note: in expansion of macro 'FOR'
   79 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:88:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:86:20: warning: unused variable 'add' [-Wunused-variable]
   86 |                 ll add = 0;
      |                    ^~~
fish.cpp:137:16: warning: unused variable 'prev' [-Wunused-variable]
  137 |             ll prev = 0;
      |                ^~~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<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++)
......
  164 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:164:9: note: in expansion of macro 'FOR'
  164 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 149936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 91848 KB Output is correct
2 Execution timed out 1049 ms 166128 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 101052 KB Output is correct
2 Correct 143 ms 101184 KB Output is correct
3 Correct 221 ms 112632 KB Output is correct
4 Correct 201 ms 110336 KB Output is correct
5 Correct 263 ms 138988 KB Output is correct
6 Correct 253 ms 138980 KB Output is correct
7 Correct 298 ms 138964 KB Output is correct
8 Correct 267 ms 138992 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 91848 KB Output is correct
2 Correct 112 ms 91980 KB Output is correct
3 Correct 92 ms 91904 KB Output is correct
4 Correct 95 ms 91844 KB Output is correct
5 Correct 98 ms 91928 KB Output is correct
6 Correct 100 ms 91844 KB Output is correct
7 Correct 96 ms 91844 KB Output is correct
8 Correct 96 ms 91816 KB Output is correct
9 Correct 107 ms 91920 KB Output is correct
10 Correct 94 ms 91944 KB Output is correct
11 Correct 106 ms 91976 KB Output is correct
12 Correct 95 ms 92164 KB Output is correct
13 Correct 94 ms 91868 KB Output is correct
14 Correct 95 ms 91980 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 91848 KB Output is correct
2 Correct 112 ms 91980 KB Output is correct
3 Correct 92 ms 91904 KB Output is correct
4 Correct 95 ms 91844 KB Output is correct
5 Correct 98 ms 91928 KB Output is correct
6 Correct 100 ms 91844 KB Output is correct
7 Correct 96 ms 91844 KB Output is correct
8 Correct 96 ms 91816 KB Output is correct
9 Correct 107 ms 91920 KB Output is correct
10 Correct 94 ms 91944 KB Output is correct
11 Correct 106 ms 91976 KB Output is correct
12 Correct 95 ms 92164 KB Output is correct
13 Correct 94 ms 91868 KB Output is correct
14 Correct 95 ms 91980 KB Output is correct
15 Correct 98 ms 92168 KB Output is correct
16 Correct 96 ms 92176 KB Output is correct
17 Correct 139 ms 110844 KB Output is correct
18 Correct 130 ms 108892 KB Output is correct
19 Correct 143 ms 110072 KB Output is correct
20 Correct 139 ms 108028 KB Output is correct
21 Correct 118 ms 107776 KB Output is correct
22 Correct 158 ms 114676 KB Output is correct
23 Correct 131 ms 105888 KB Output is correct
24 Correct 139 ms 111772 KB Output is correct
25 Correct 109 ms 92292 KB Output is correct
26 Correct 133 ms 104696 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 91848 KB Output is correct
2 Correct 112 ms 91980 KB Output is correct
3 Correct 92 ms 91904 KB Output is correct
4 Correct 95 ms 91844 KB Output is correct
5 Correct 98 ms 91928 KB Output is correct
6 Correct 100 ms 91844 KB Output is correct
7 Correct 96 ms 91844 KB Output is correct
8 Correct 96 ms 91816 KB Output is correct
9 Correct 107 ms 91920 KB Output is correct
10 Correct 94 ms 91944 KB Output is correct
11 Correct 106 ms 91976 KB Output is correct
12 Correct 95 ms 92164 KB Output is correct
13 Correct 94 ms 91868 KB Output is correct
14 Correct 95 ms 91980 KB Output is correct
15 Correct 98 ms 92168 KB Output is correct
16 Correct 96 ms 92176 KB Output is correct
17 Correct 139 ms 110844 KB Output is correct
18 Correct 130 ms 108892 KB Output is correct
19 Correct 143 ms 110072 KB Output is correct
20 Correct 139 ms 108028 KB Output is correct
21 Correct 118 ms 107776 KB Output is correct
22 Correct 158 ms 114676 KB Output is correct
23 Correct 131 ms 105888 KB Output is correct
24 Correct 139 ms 111772 KB Output is correct
25 Correct 109 ms 92292 KB Output is correct
26 Correct 133 ms 104696 KB Output is correct
27 Correct 89 ms 93704 KB Output is correct
28 Correct 512 ms 159032 KB Output is correct
29 Execution timed out 1050 ms 243180 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 101052 KB Output is correct
2 Correct 143 ms 101184 KB Output is correct
3 Correct 221 ms 112632 KB Output is correct
4 Correct 201 ms 110336 KB Output is correct
5 Correct 263 ms 138988 KB Output is correct
6 Correct 253 ms 138980 KB Output is correct
7 Correct 298 ms 138964 KB Output is correct
8 Correct 267 ms 138992 KB Output is correct
9 Correct 356 ms 219888 KB Output is correct
10 Correct 225 ms 114172 KB Output is correct
11 Correct 381 ms 146164 KB Output is correct
12 Correct 112 ms 91936 KB Output is correct
13 Correct 99 ms 91848 KB Output is correct
14 Correct 85 ms 91844 KB Output is correct
15 Correct 100 ms 91792 KB Output is correct
16 Correct 94 ms 91844 KB Output is correct
17 Correct 117 ms 91852 KB Output is correct
18 Correct 178 ms 101224 KB Output is correct
19 Correct 192 ms 101052 KB Output is correct
20 Correct 144 ms 101052 KB Output is correct
21 Correct 153 ms 101048 KB Output is correct
22 Correct 416 ms 217952 KB Output is correct
23 Correct 744 ms 220356 KB Output is correct
24 Correct 547 ms 231104 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 149936 KB Time limit exceeded
2 Halted 0 ms 0 KB -