oj.uz

Submission #1070792

# Submission time Handle Problem Language Result Execution time Memory
1070792 2024-08-22T18:35:58 Z beaconmc Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 400776 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;


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 Correct 492 ms 282988 KB Output is correct
2 Correct 575 ms 322620 KB Output is correct
3 Correct 323 ms 214100 KB Output is correct
4 Correct 308 ms 214096 KB Output is correct
5 Execution timed out 1039 ms 331692 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 107604 KB Output is correct
2 Correct 876 ms 338364 KB Output is correct
3 Correct 948 ms 372424 KB Output is correct
4 Correct 471 ms 283076 KB Output is correct
5 Correct 550 ms 322776 KB Output is correct
6 Correct 60 ms 107600 KB Output is correct
7 Correct 60 ms 107600 KB Output is correct
8 Correct 116 ms 107600 KB Output is correct
9 Correct 64 ms 107604 KB Output is correct
10 Correct 199 ms 214036 KB Output is correct
11 Correct 233 ms 213936 KB Output is correct
12 Correct 646 ms 314604 KB Output is correct
13 Correct 845 ms 365712 KB Output is correct
14 Correct 648 ms 298796 KB Output is correct
15 Correct 528 ms 290616 KB Output is correct
16 Correct 639 ms 298968 KB Output is correct
17 Correct 809 ms 334268 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 214096 KB Output is correct
2 Correct 335 ms 214100 KB Output is correct
3 Correct 298 ms 231764 KB Output is correct
4 Correct 389 ms 236368 KB Output is correct
5 Correct 395 ms 263252 KB Output is correct
6 Correct 543 ms 263244 KB Output is correct
7 Correct 527 ms 263248 KB Output is correct
8 Correct 420 ms 263248 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 107604 KB Output is correct
2 Correct 66 ms 107604 KB Output is correct
3 Correct 77 ms 107600 KB Output is correct
4 Correct 65 ms 107600 KB Output is correct
5 Correct 65 ms 107604 KB Output is correct
6 Correct 79 ms 107596 KB Output is correct
7 Correct 63 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 68 ms 107860 KB Output is correct
10 Correct 100 ms 108680 KB Output is correct
11 Correct 95 ms 108208 KB Output is correct
12 Correct 99 ms 108628 KB Output is correct
13 Correct 64 ms 107600 KB Output is correct
14 Correct 105 ms 108440 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 107604 KB Output is correct
2 Correct 66 ms 107604 KB Output is correct
3 Correct 77 ms 107600 KB Output is correct
4 Correct 65 ms 107600 KB Output is correct
5 Correct 65 ms 107604 KB Output is correct
6 Correct 79 ms 107596 KB Output is correct
7 Correct 63 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 68 ms 107860 KB Output is correct
10 Correct 100 ms 108680 KB Output is correct
11 Correct 95 ms 108208 KB Output is correct
12 Correct 99 ms 108628 KB Output is correct
13 Correct 64 ms 107600 KB Output is correct
14 Correct 105 ms 108440 KB Output is correct
15 Correct 78 ms 108356 KB Output is correct
16 Correct 71 ms 109196 KB Output is correct
17 Correct 209 ms 140112 KB Output is correct
18 Correct 183 ms 134408 KB Output is correct
19 Correct 189 ms 138280 KB Output is correct
20 Correct 179 ms 131020 KB Output is correct
21 Correct 175 ms 130368 KB Output is correct
22 Correct 279 ms 153424 KB Output is correct
23 Correct 128 ms 123984 KB Output is correct
24 Correct 238 ms 144672 KB Output is correct
25 Correct 68 ms 109136 KB Output is correct
26 Correct 111 ms 119892 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 107604 KB Output is correct
2 Correct 66 ms 107604 KB Output is correct
3 Correct 77 ms 107600 KB Output is correct
4 Correct 65 ms 107600 KB Output is correct
5 Correct 65 ms 107604 KB Output is correct
6 Correct 79 ms 107596 KB Output is correct
7 Correct 63 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 68 ms 107860 KB Output is correct
10 Correct 100 ms 108680 KB Output is correct
11 Correct 95 ms 108208 KB Output is correct
12 Correct 99 ms 108628 KB Output is correct
13 Correct 64 ms 107600 KB Output is correct
14 Correct 105 ms 108440 KB Output is correct
15 Correct 78 ms 108356 KB Output is correct
16 Correct 71 ms 109196 KB Output is correct
17 Correct 209 ms 140112 KB Output is correct
18 Correct 183 ms 134408 KB Output is correct
19 Correct 189 ms 138280 KB Output is correct
20 Correct 179 ms 131020 KB Output is correct
21 Correct 175 ms 130368 KB Output is correct
22 Correct 279 ms 153424 KB Output is correct
23 Correct 128 ms 123984 KB Output is correct
24 Correct 238 ms 144672 KB Output is correct
25 Correct 68 ms 109136 KB Output is correct
26 Correct 111 ms 119892 KB Output is correct
27 Correct 123 ms 116052 KB Output is correct
28 Correct 726 ms 238928 KB Output is correct
29 Execution timed out 1072 ms 321108 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 214096 KB Output is correct
2 Correct 335 ms 214100 KB Output is correct
3 Correct 298 ms 231764 KB Output is correct
4 Correct 389 ms 236368 KB Output is correct
5 Correct 395 ms 263252 KB Output is correct
6 Correct 543 ms 263244 KB Output is correct
7 Correct 527 ms 263248 KB Output is correct
8 Correct 420 ms 263248 KB Output is correct
9 Correct 805 ms 394832 KB Output is correct
10 Correct 310 ms 203860 KB Output is correct
11 Correct 624 ms 300096 KB Output is correct
12 Correct 74 ms 107604 KB Output is correct
13 Correct 59 ms 107640 KB Output is correct
14 Correct 59 ms 107556 KB Output is correct
15 Correct 71 ms 107524 KB Output is correct
16 Correct 62 ms 107604 KB Output is correct
17 Correct 88 ms 107468 KB Output is correct
18 Correct 305 ms 214064 KB Output is correct
19 Correct 196 ms 214096 KB Output is correct
20 Correct 202 ms 213884 KB Output is correct
21 Correct 190 ms 214100 KB Output is correct
22 Correct 808 ms 391760 KB Output is correct
23 Execution timed out 1004 ms 400776 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 282988 KB Output is correct
2 Correct 575 ms 322620 KB Output is correct
3 Correct 323 ms 214100 KB Output is correct
4 Correct 308 ms 214096 KB Output is correct
5 Execution timed out 1039 ms 331692 KB Time limit exceeded
6 Halted 0 ms 0 KB -