oj.uz

Submission #1077865

# Submission time Handle Problem Language Result Execution time Memory
1077865 2024-08-27T09:52:33 Z beaconmc Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 297496 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;
     
     
    basic_string<ll> realheights[maxn];
     
    unordered_map<int, unordered_map<int,int>> 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]][Y[i]] = W[i];
     
            if (X[i] > 0) realheights[X[i]-1].push_back(Y[i]);
            if (X[i] > 1) realheights[X[i]-2].push_back(Y[i]);
            realheights[X[i]].push_back(Y[i]);
            realheights[X[i]+1].push_back(Y[i]);
            realheights[X[i]+2].push_back(Y[i]);
        }
        FOR(i,0,maxn) realheights[i].push_back(0);
        FOR(i,0,maxn) realheights[i].push_back(maxn);
     
        FOR(i,0,maxn){
            sort(realheights[i].begin(), realheights[i].end());
            auto it = unique(realheights[i].begin(), realheights[i].end());
            realheights[i].resize(it-realheights[i].begin());
            sort(realheights[i].begin(), realheights[i].end());
        }
     
        FOR(i,0,maxn){
            FOR(k,0,2){
                pref[i][k].resize(realheights[i].size());
                pref2[i][k].resize(realheights[i].size());
                suff[i][k].resize(realheights[i].size());
            }
            p[i].resize(realheights[i].size());
            dp[i].resize(realheights[i].size());
        }
     
     
     
     
        FOR(i,0,maxn){
            p[i][0] = 0;
            ll prev = 0;
            FOR(j,1,realheights[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;
     
        }
     
     
     
     
     
     
        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:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   68 |             FOR(j,1,realheights[i].size()){
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:68:13: note: in expansion of macro 'FOR'
   68 |             FOR(j,1,realheights[i].size()){
      |             ^~~
fish.cpp:67:16: warning: unused variable 'prev' [-Wunused-variable]
   67 |             ll prev = 0;
      |                ^~~~
fish.cpp:9:37: 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++)
......
   77 |             FOR(X,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:77:13: note: in expansion of macro 'FOR'
   77 |             FOR(X,0,dp[i].size()){
      |             ^~~
fish.cpp:86:30: 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]
   86 |                         if (X==dp[i].size()-1) continue;
      |                             ~^~~~~~~~~~~~~~~~
fish.cpp:84:24: warning: unused variable 'add' [-Wunused-variable]
   84 |                     ll add = 0;
      |                        ^~~
fish.cpp:135:20: warning: unused variable 'prev' [-Wunused-variable]
  135 |                 ll prev = 0;
      |                    ^~~~
fish.cpp:9:37: 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++)
......
  162 |             FOR(j,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:162:13: note: in expansion of macro 'FOR'
  162 |             FOR(j,0,dp[i].size()){
      |             ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 117416 KB Output is correct
2 Correct 213 ms 126612 KB Output is correct
3 Correct 97 ms 86216 KB Output is correct
4 Correct 110 ms 86124 KB Output is correct
5 Correct 917 ms 297496 KB Output is correct
6 Execution timed out 1096 ms 293236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 83144 KB Output is correct
2 Correct 310 ms 136168 KB Output is correct
3 Correct 360 ms 144552 KB Output is correct
4 Correct 203 ms 117416 KB Output is correct
5 Correct 250 ms 126664 KB Output is correct
6 Correct 129 ms 83144 KB Output is correct
7 Correct 93 ms 83140 KB Output is correct
8 Correct 82 ms 83124 KB Output is correct
9 Correct 97 ms 82964 KB Output is correct
10 Correct 98 ms 86120 KB Output is correct
11 Correct 113 ms 86212 KB Output is correct
12 Correct 212 ms 127260 KB Output is correct
13 Correct 272 ms 139032 KB Output is correct
14 Correct 212 ms 122256 KB Output is correct
15 Correct 227 ms 114224 KB Output is correct
16 Correct 213 ms 122292 KB Output is correct
17 Correct 247 ms 128660 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 86212 KB Output is correct
2 Correct 144 ms 86216 KB Output is correct
3 Correct 192 ms 100568 KB Output is correct
4 Correct 168 ms 97480 KB Output is correct
5 Correct 261 ms 110784 KB Output is correct
6 Correct 283 ms 110276 KB Output is correct
7 Correct 274 ms 110792 KB Output is correct
8 Correct 255 ms 110900 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 83068 KB Output is correct
2 Correct 79 ms 83004 KB Output is correct
3 Correct 96 ms 83144 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 105 ms 82944 KB Output is correct
6 Correct 77 ms 83144 KB Output is correct
7 Correct 78 ms 83144 KB Output is correct
8 Correct 80 ms 83140 KB Output is correct
9 Correct 95 ms 83140 KB Output is correct
10 Correct 85 ms 83652 KB Output is correct
11 Correct 88 ms 83580 KB Output is correct
12 Correct 80 ms 83400 KB Output is correct
13 Correct 82 ms 83140 KB Output is correct
14 Correct 81 ms 83400 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 83068 KB Output is correct
2 Correct 79 ms 83004 KB Output is correct
3 Correct 96 ms 83144 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 105 ms 82944 KB Output is correct
6 Correct 77 ms 83144 KB Output is correct
7 Correct 78 ms 83144 KB Output is correct
8 Correct 80 ms 83140 KB Output is correct
9 Correct 95 ms 83140 KB Output is correct
10 Correct 85 ms 83652 KB Output is correct
11 Correct 88 ms 83580 KB Output is correct
12 Correct 80 ms 83400 KB Output is correct
13 Correct 82 ms 83140 KB Output is correct
14 Correct 81 ms 83400 KB Output is correct
15 Correct 82 ms 83400 KB Output is correct
16 Correct 94 ms 83652 KB Output is correct
17 Correct 150 ms 95428 KB Output is correct
18 Correct 145 ms 93380 KB Output is correct
19 Correct 133 ms 94864 KB Output is correct
20 Correct 128 ms 92872 KB Output is correct
21 Correct 130 ms 92416 KB Output is correct
22 Correct 193 ms 102088 KB Output is correct
23 Correct 107 ms 88688 KB Output is correct
24 Correct 131 ms 95172 KB Output is correct
25 Correct 82 ms 83620 KB Output is correct
26 Correct 126 ms 87240 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 83068 KB Output is correct
2 Correct 79 ms 83004 KB Output is correct
3 Correct 96 ms 83144 KB Output is correct
4 Correct 77 ms 83144 KB Output is correct
5 Correct 105 ms 82944 KB Output is correct
6 Correct 77 ms 83144 KB Output is correct
7 Correct 78 ms 83144 KB Output is correct
8 Correct 80 ms 83140 KB Output is correct
9 Correct 95 ms 83140 KB Output is correct
10 Correct 85 ms 83652 KB Output is correct
11 Correct 88 ms 83580 KB Output is correct
12 Correct 80 ms 83400 KB Output is correct
13 Correct 82 ms 83140 KB Output is correct
14 Correct 81 ms 83400 KB Output is correct
15 Correct 82 ms 83400 KB Output is correct
16 Correct 94 ms 83652 KB Output is correct
17 Correct 150 ms 95428 KB Output is correct
18 Correct 145 ms 93380 KB Output is correct
19 Correct 133 ms 94864 KB Output is correct
20 Correct 128 ms 92872 KB Output is correct
21 Correct 130 ms 92416 KB Output is correct
22 Correct 193 ms 102088 KB Output is correct
23 Correct 107 ms 88688 KB Output is correct
24 Correct 131 ms 95172 KB Output is correct
25 Correct 82 ms 83620 KB Output is correct
26 Correct 126 ms 87240 KB Output is correct
27 Correct 105 ms 85084 KB Output is correct
28 Correct 309 ms 133576 KB Output is correct
29 Correct 562 ms 186344 KB Output is correct
30 Correct 853 ms 272328 KB Output is correct
31 Correct 809 ms 264120 KB Output is correct
32 Correct 365 ms 144836 KB Output is correct
33 Correct 875 ms 284868 KB Output is correct
34 Correct 882 ms 285112 KB Output is correct
35 Correct 285 ms 131064 KB Output is correct
36 Correct 716 ms 227784 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 86212 KB Output is correct
2 Correct 144 ms 86216 KB Output is correct
3 Correct 192 ms 100568 KB Output is correct
4 Correct 168 ms 97480 KB Output is correct
5 Correct 261 ms 110784 KB Output is correct
6 Correct 283 ms 110276 KB Output is correct
7 Correct 274 ms 110792 KB Output is correct
8 Correct 255 ms 110900 KB Output is correct
9 Correct 398 ms 154496 KB Output is correct
10 Correct 233 ms 104388 KB Output is correct
11 Correct 362 ms 125636 KB Output is correct
12 Correct 80 ms 83144 KB Output is correct
13 Correct 81 ms 83144 KB Output is correct
14 Correct 77 ms 83196 KB Output is correct
15 Correct 72 ms 83024 KB Output is correct
16 Correct 78 ms 83140 KB Output is correct
17 Correct 89 ms 83140 KB Output is correct
18 Correct 98 ms 86212 KB Output is correct
19 Correct 113 ms 86208 KB Output is correct
20 Correct 94 ms 86212 KB Output is correct
21 Correct 95 ms 86212 KB Output is correct
22 Correct 510 ms 152296 KB Output is correct
23 Correct 495 ms 161220 KB Output is correct
24 Correct 586 ms 172392 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 117416 KB Output is correct
2 Correct 213 ms 126612 KB Output is correct
3 Correct 97 ms 86216 KB Output is correct
4 Correct 110 ms 86124 KB Output is correct
5 Correct 917 ms 297496 KB Output is correct
6 Execution timed out 1096 ms 293236 KB Time limit exceeded
7 Halted 0 ms 0 KB -