oj.uz

Submission #1070869

# Submission time Handle Problem Language Result Execution time Memory
1070869 2024-08-22T20:12:45 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 374936 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 220 ms 138084 KB Output is correct
2 Correct 251 ms 149936 KB Output is correct
3 Correct 87 ms 96592 KB Output is correct
4 Correct 76 ms 96540 KB Output is correct
5 Execution timed out 1080 ms 374936 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 93520 KB Output is correct
2 Correct 413 ms 159432 KB Output is correct
3 Correct 405 ms 169532 KB Output is correct
4 Correct 227 ms 138088 KB Output is correct
5 Correct 260 ms 149912 KB Output is correct
6 Correct 84 ms 93524 KB Output is correct
7 Correct 65 ms 93524 KB Output is correct
8 Correct 67 ms 93512 KB Output is correct
9 Correct 67 ms 93520 KB Output is correct
10 Correct 75 ms 96612 KB Output is correct
11 Correct 92 ms 96564 KB Output is correct
12 Correct 274 ms 151772 KB Output is correct
13 Correct 312 ms 167108 KB Output is correct
14 Correct 255 ms 145120 KB Output is correct
15 Correct 219 ms 131696 KB Output is correct
16 Correct 302 ms 145140 KB Output is correct
17 Correct 308 ms 152648 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 96592 KB Output is correct
2 Correct 81 ms 96600 KB Output is correct
3 Correct 144 ms 110676 KB Output is correct
4 Correct 127 ms 108348 KB Output is correct
5 Correct 213 ms 120916 KB Output is correct
6 Correct 173 ms 120920 KB Output is correct
7 Correct 209 ms 120912 KB Output is correct
8 Correct 171 ms 120916 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 93496 KB Output is correct
2 Correct 75 ms 93520 KB Output is correct
3 Correct 79 ms 93524 KB Output is correct
4 Correct 64 ms 93524 KB Output is correct
5 Correct 86 ms 93452 KB Output is correct
6 Correct 62 ms 93520 KB Output is correct
7 Correct 72 ms 93524 KB Output is correct
8 Correct 75 ms 93524 KB Output is correct
9 Correct 61 ms 93524 KB Output is correct
10 Correct 66 ms 93780 KB Output is correct
11 Correct 78 ms 93780 KB Output is correct
12 Correct 70 ms 93780 KB Output is correct
13 Correct 64 ms 93388 KB Output is correct
14 Correct 65 ms 93776 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 93496 KB Output is correct
2 Correct 75 ms 93520 KB Output is correct
3 Correct 79 ms 93524 KB Output is correct
4 Correct 64 ms 93524 KB Output is correct
5 Correct 86 ms 93452 KB Output is correct
6 Correct 62 ms 93520 KB Output is correct
7 Correct 72 ms 93524 KB Output is correct
8 Correct 75 ms 93524 KB Output is correct
9 Correct 61 ms 93524 KB Output is correct
10 Correct 66 ms 93780 KB Output is correct
11 Correct 78 ms 93780 KB Output is correct
12 Correct 70 ms 93780 KB Output is correct
13 Correct 64 ms 93388 KB Output is correct
14 Correct 65 ms 93776 KB Output is correct
15 Correct 72 ms 93776 KB Output is correct
16 Correct 84 ms 94040 KB Output is correct
17 Correct 145 ms 106580 KB Output is correct
18 Correct 131 ms 104016 KB Output is correct
19 Correct 130 ms 105644 KB Output is correct
20 Correct 129 ms 102740 KB Output is correct
21 Correct 122 ms 102480 KB Output is correct
22 Correct 171 ms 111440 KB Output is correct
23 Correct 113 ms 100436 KB Output is correct
24 Correct 145 ms 108368 KB Output is correct
25 Correct 94 ms 94032 KB Output is correct
26 Correct 103 ms 98492 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 93496 KB Output is correct
2 Correct 75 ms 93520 KB Output is correct
3 Correct 79 ms 93524 KB Output is correct
4 Correct 64 ms 93524 KB Output is correct
5 Correct 86 ms 93452 KB Output is correct
6 Correct 62 ms 93520 KB Output is correct
7 Correct 72 ms 93524 KB Output is correct
8 Correct 75 ms 93524 KB Output is correct
9 Correct 61 ms 93524 KB Output is correct
10 Correct 66 ms 93780 KB Output is correct
11 Correct 78 ms 93780 KB Output is correct
12 Correct 70 ms 93780 KB Output is correct
13 Correct 64 ms 93388 KB Output is correct
14 Correct 65 ms 93776 KB Output is correct
15 Correct 72 ms 93776 KB Output is correct
16 Correct 84 ms 94040 KB Output is correct
17 Correct 145 ms 106580 KB Output is correct
18 Correct 131 ms 104016 KB Output is correct
19 Correct 130 ms 105644 KB Output is correct
20 Correct 129 ms 102740 KB Output is correct
21 Correct 122 ms 102480 KB Output is correct
22 Correct 171 ms 111440 KB Output is correct
23 Correct 113 ms 100436 KB Output is correct
24 Correct 145 ms 108368 KB Output is correct
25 Correct 94 ms 94032 KB Output is correct
26 Correct 103 ms 98492 KB Output is correct
27 Correct 84 ms 96336 KB Output is correct
28 Correct 402 ms 146036 KB Output is correct
29 Correct 784 ms 213584 KB Output is correct
30 Execution timed out 1053 ms 332168 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 96592 KB Output is correct
2 Correct 81 ms 96600 KB Output is correct
3 Correct 144 ms 110676 KB Output is correct
4 Correct 127 ms 108348 KB Output is correct
5 Correct 213 ms 120916 KB Output is correct
6 Correct 173 ms 120920 KB Output is correct
7 Correct 209 ms 120912 KB Output is correct
8 Correct 171 ms 120916 KB Output is correct
9 Correct 383 ms 186712 KB Output is correct
10 Correct 173 ms 113232 KB Output is correct
11 Correct 264 ms 132692 KB Output is correct
12 Correct 67 ms 93524 KB Output is correct
13 Correct 90 ms 93520 KB Output is correct
14 Correct 68 ms 93520 KB Output is correct
15 Correct 65 ms 93460 KB Output is correct
16 Correct 67 ms 93520 KB Output is correct
17 Correct 68 ms 93524 KB Output is correct
18 Correct 94 ms 96592 KB Output is correct
19 Correct 73 ms 96592 KB Output is correct
20 Correct 73 ms 96488 KB Output is correct
21 Correct 93 ms 96592 KB Output is correct
22 Correct 402 ms 184916 KB Output is correct
23 Correct 439 ms 185684 KB Output is correct
24 Correct 514 ms 202676 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 138084 KB Output is correct
2 Correct 251 ms 149936 KB Output is correct
3 Correct 87 ms 96592 KB Output is correct
4 Correct 76 ms 96540 KB Output is correct
5 Execution timed out 1080 ms 374936 KB Time limit exceeded
6 Halted 0 ms 0 KB -