oj.uz

Submission #1070881

# Submission time Handle Problem Language Result Execution time Memory
1070881 2024-08-22T20:18:50 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 363276 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];
basic_string<ll> realheights[maxn];
 

unordered_map<ll,ll> weights[maxn];
 
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]][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);
    }


 
    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][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][realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[i-1][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;
 
    }
 
 
    // 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::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++)
......
   64 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:64:9: note: in expansion of macro 'FOR'
   64 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:63:12: warning: unused variable 'prev' [-Wunused-variable]
   63 |         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++)
......
   73 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:73:9: note: in expansion of macro 'FOR'
   73 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:82: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]
   82 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:80:20: warning: unused variable 'add' [-Wunused-variable]
   80 |                 ll add = 0;
      |                    ^~~
fish.cpp:130:16: warning: unused variable 'prev' [-Wunused-variable]
  130 |             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++)
......
  157 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:157:9: note: in expansion of macro 'FOR'
  157 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 138084 KB Output is correct
2 Correct 302 ms 149960 KB Output is correct
3 Correct 86 ms 96592 KB Output is correct
4 Correct 84 ms 96460 KB Output is correct
5 Execution timed out 1052 ms 363276 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 93344 KB Output is correct
2 Correct 448 ms 159336 KB Output is correct
3 Correct 538 ms 169404 KB Output is correct
4 Correct 247 ms 138064 KB Output is correct
5 Correct 277 ms 150368 KB Output is correct
6 Correct 70 ms 93568 KB Output is correct
7 Correct 71 ms 93576 KB Output is correct
8 Correct 69 ms 93520 KB Output is correct
9 Correct 69 ms 93332 KB Output is correct
10 Correct 91 ms 96592 KB Output is correct
11 Correct 85 ms 96596 KB Output is correct
12 Correct 305 ms 151772 KB Output is correct
13 Correct 371 ms 167108 KB Output is correct
14 Correct 323 ms 145128 KB Output is correct
15 Correct 237 ms 131820 KB Output is correct
16 Correct 291 ms 145144 KB Output is correct
17 Correct 378 ms 152832 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 96592 KB Output is correct
2 Correct 109 ms 96640 KB Output is correct
3 Correct 146 ms 110672 KB Output is correct
4 Correct 144 ms 108444 KB Output is correct
5 Correct 227 ms 120872 KB Output is correct
6 Correct 208 ms 120824 KB Output is correct
7 Correct 223 ms 120788 KB Output is correct
8 Correct 209 ms 120764 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93512 KB Output is correct
2 Correct 72 ms 93520 KB Output is correct
3 Correct 90 ms 93456 KB Output is correct
4 Correct 67 ms 93412 KB Output is correct
5 Correct 87 ms 93524 KB Output is correct
6 Correct 70 ms 93348 KB Output is correct
7 Correct 79 ms 93380 KB Output is correct
8 Correct 72 ms 93520 KB Output is correct
9 Correct 82 ms 93520 KB Output is correct
10 Correct 75 ms 94024 KB Output is correct
11 Correct 72 ms 93568 KB Output is correct
12 Correct 71 ms 93884 KB Output is correct
13 Correct 102 ms 93524 KB Output is correct
14 Correct 105 ms 93780 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93512 KB Output is correct
2 Correct 72 ms 93520 KB Output is correct
3 Correct 90 ms 93456 KB Output is correct
4 Correct 67 ms 93412 KB Output is correct
5 Correct 87 ms 93524 KB Output is correct
6 Correct 70 ms 93348 KB Output is correct
7 Correct 79 ms 93380 KB Output is correct
8 Correct 72 ms 93520 KB Output is correct
9 Correct 82 ms 93520 KB Output is correct
10 Correct 75 ms 94024 KB Output is correct
11 Correct 72 ms 93568 KB Output is correct
12 Correct 71 ms 93884 KB Output is correct
13 Correct 102 ms 93524 KB Output is correct
14 Correct 105 ms 93780 KB Output is correct
15 Correct 87 ms 93608 KB Output is correct
16 Correct 101 ms 94036 KB Output is correct
17 Correct 145 ms 106580 KB Output is correct
18 Correct 143 ms 104020 KB Output is correct
19 Correct 163 ms 105808 KB Output is correct
20 Correct 156 ms 103000 KB Output is correct
21 Correct 135 ms 102552 KB Output is correct
22 Correct 191 ms 111444 KB Output is correct
23 Correct 105 ms 100436 KB Output is correct
24 Correct 159 ms 108368 KB Output is correct
25 Correct 74 ms 94100 KB Output is correct
26 Correct 117 ms 98420 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93512 KB Output is correct
2 Correct 72 ms 93520 KB Output is correct
3 Correct 90 ms 93456 KB Output is correct
4 Correct 67 ms 93412 KB Output is correct
5 Correct 87 ms 93524 KB Output is correct
6 Correct 70 ms 93348 KB Output is correct
7 Correct 79 ms 93380 KB Output is correct
8 Correct 72 ms 93520 KB Output is correct
9 Correct 82 ms 93520 KB Output is correct
10 Correct 75 ms 94024 KB Output is correct
11 Correct 72 ms 93568 KB Output is correct
12 Correct 71 ms 93884 KB Output is correct
13 Correct 102 ms 93524 KB Output is correct
14 Correct 105 ms 93780 KB Output is correct
15 Correct 87 ms 93608 KB Output is correct
16 Correct 101 ms 94036 KB Output is correct
17 Correct 145 ms 106580 KB Output is correct
18 Correct 143 ms 104020 KB Output is correct
19 Correct 163 ms 105808 KB Output is correct
20 Correct 156 ms 103000 KB Output is correct
21 Correct 135 ms 102552 KB Output is correct
22 Correct 191 ms 111444 KB Output is correct
23 Correct 105 ms 100436 KB Output is correct
24 Correct 159 ms 108368 KB Output is correct
25 Correct 74 ms 94100 KB Output is correct
26 Correct 117 ms 98420 KB Output is correct
27 Correct 82 ms 96244 KB Output is correct
28 Correct 478 ms 146272 KB Output is correct
29 Execution timed out 1004 ms 213424 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 96592 KB Output is correct
2 Correct 109 ms 96640 KB Output is correct
3 Correct 146 ms 110672 KB Output is correct
4 Correct 144 ms 108444 KB Output is correct
5 Correct 227 ms 120872 KB Output is correct
6 Correct 208 ms 120824 KB Output is correct
7 Correct 223 ms 120788 KB Output is correct
8 Correct 209 ms 120764 KB Output is correct
9 Correct 419 ms 186704 KB Output is correct
10 Correct 194 ms 112976 KB Output is correct
11 Correct 369 ms 132552 KB Output is correct
12 Correct 73 ms 93520 KB Output is correct
13 Correct 68 ms 93436 KB Output is correct
14 Correct 71 ms 93520 KB Output is correct
15 Correct 76 ms 93524 KB Output is correct
16 Correct 86 ms 93524 KB Output is correct
17 Correct 71 ms 93524 KB Output is correct
18 Correct 121 ms 96592 KB Output is correct
19 Correct 99 ms 96684 KB Output is correct
20 Correct 90 ms 96592 KB Output is correct
21 Correct 84 ms 96640 KB Output is correct
22 Correct 483 ms 184616 KB Output is correct
23 Correct 535 ms 185688 KB Output is correct
24 Correct 562 ms 202836 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 138084 KB Output is correct
2 Correct 302 ms 149960 KB Output is correct
3 Correct 86 ms 96592 KB Output is correct
4 Correct 84 ms 96460 KB Output is correct
5 Execution timed out 1052 ms 363276 KB Time limit exceeded
6 Halted 0 ms 0 KB -