oj.uz

Submission #1070915

# Submission time Handle Problem Language Result Execution time Memory
1070915 2024-08-22T20:45:30 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 353788 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;

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
 
unordered_set<ll> heights[maxn];
basic_string<ll> realheights[maxn];
 
 
unordered_map<ll, ll, chash> 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:10: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]
   10 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   71 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:71:9: note: in expansion of macro 'FOR'
   71 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:70:12: warning: unused variable 'prev' [-Wunused-variable]
   70 |         ll prev = 0;
      |            ^~~~
fish.cpp:10: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]
   10 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   80 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:80:9: note: in expansion of macro 'FOR'
   80 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:89: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]
   89 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:87:20: warning: unused variable 'add' [-Wunused-variable]
   87 |                 ll add = 0;
      |                    ^~~
fish.cpp:138:16: warning: unused variable 'prev' [-Wunused-variable]
  138 |             ll prev = 0;
      |                ^~~~
fish.cpp:10: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]
   10 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  165 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:165:9: note: in expansion of macro 'FOR'
  165 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 138916 KB Output is correct
2 Correct 415 ms 150984 KB Output is correct
3 Correct 136 ms 94600 KB Output is correct
4 Correct 130 ms 94712 KB Output is correct
5 Execution timed out 1062 ms 333108 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 88516 KB Output is correct
2 Correct 553 ms 159960 KB Output is correct
3 Correct 721 ms 170300 KB Output is correct
4 Correct 369 ms 138920 KB Output is correct
5 Correct 378 ms 150980 KB Output is correct
6 Correct 84 ms 88516 KB Output is correct
7 Correct 91 ms 88628 KB Output is correct
8 Correct 102 ms 88520 KB Output is correct
9 Correct 83 ms 88516 KB Output is correct
10 Correct 116 ms 94660 KB Output is correct
11 Correct 120 ms 94636 KB Output is correct
12 Correct 400 ms 152368 KB Output is correct
13 Correct 572 ms 168020 KB Output is correct
14 Correct 472 ms 145720 KB Output is correct
15 Correct 395 ms 133668 KB Output is correct
16 Correct 411 ms 145812 KB Output is correct
17 Correct 477 ms 153800 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 94832 KB Output is correct
2 Correct 123 ms 94592 KB Output is correct
3 Correct 195 ms 108632 KB Output is correct
4 Correct 180 ms 106624 KB Output is correct
5 Correct 307 ms 119008 KB Output is correct
6 Correct 303 ms 118912 KB Output is correct
7 Correct 243 ms 118836 KB Output is correct
8 Correct 246 ms 118912 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 88588 KB Output is correct
2 Correct 76 ms 88496 KB Output is correct
3 Correct 97 ms 88504 KB Output is correct
4 Correct 90 ms 88516 KB Output is correct
5 Correct 83 ms 88644 KB Output is correct
6 Correct 81 ms 88520 KB Output is correct
7 Correct 92 ms 88516 KB Output is correct
8 Correct 105 ms 88520 KB Output is correct
9 Correct 84 ms 88772 KB Output is correct
10 Correct 104 ms 89064 KB Output is correct
11 Correct 78 ms 88692 KB Output is correct
12 Correct 98 ms 89032 KB Output is correct
13 Correct 77 ms 88524 KB Output is correct
14 Correct 81 ms 88860 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 88588 KB Output is correct
2 Correct 76 ms 88496 KB Output is correct
3 Correct 97 ms 88504 KB Output is correct
4 Correct 90 ms 88516 KB Output is correct
5 Correct 83 ms 88644 KB Output is correct
6 Correct 81 ms 88520 KB Output is correct
7 Correct 92 ms 88516 KB Output is correct
8 Correct 105 ms 88520 KB Output is correct
9 Correct 84 ms 88772 KB Output is correct
10 Correct 104 ms 89064 KB Output is correct
11 Correct 78 ms 88692 KB Output is correct
12 Correct 98 ms 89032 KB Output is correct
13 Correct 77 ms 88524 KB Output is correct
14 Correct 81 ms 88860 KB Output is correct
15 Correct 93 ms 88840 KB Output is correct
16 Correct 93 ms 89172 KB Output is correct
17 Correct 156 ms 101576 KB Output is correct
18 Correct 167 ms 99044 KB Output is correct
19 Correct 160 ms 100804 KB Output is correct
20 Correct 133 ms 97988 KB Output is correct
21 Correct 153 ms 97528 KB Output is correct
22 Correct 199 ms 108548 KB Output is correct
23 Correct 111 ms 95436 KB Output is correct
24 Correct 167 ms 105700 KB Output is correct
25 Correct 100 ms 89284 KB Output is correct
26 Correct 111 ms 93652 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 88588 KB Output is correct
2 Correct 76 ms 88496 KB Output is correct
3 Correct 97 ms 88504 KB Output is correct
4 Correct 90 ms 88516 KB Output is correct
5 Correct 83 ms 88644 KB Output is correct
6 Correct 81 ms 88520 KB Output is correct
7 Correct 92 ms 88516 KB Output is correct
8 Correct 105 ms 88520 KB Output is correct
9 Correct 84 ms 88772 KB Output is correct
10 Correct 104 ms 89064 KB Output is correct
11 Correct 78 ms 88692 KB Output is correct
12 Correct 98 ms 89032 KB Output is correct
13 Correct 77 ms 88524 KB Output is correct
14 Correct 81 ms 88860 KB Output is correct
15 Correct 93 ms 88840 KB Output is correct
16 Correct 93 ms 89172 KB Output is correct
17 Correct 156 ms 101576 KB Output is correct
18 Correct 167 ms 99044 KB Output is correct
19 Correct 160 ms 100804 KB Output is correct
20 Correct 133 ms 97988 KB Output is correct
21 Correct 153 ms 97528 KB Output is correct
22 Correct 199 ms 108548 KB Output is correct
23 Correct 111 ms 95436 KB Output is correct
24 Correct 167 ms 105700 KB Output is correct
25 Correct 100 ms 89284 KB Output is correct
26 Correct 111 ms 93652 KB Output is correct
27 Correct 92 ms 91336 KB Output is correct
28 Correct 430 ms 146812 KB Output is correct
29 Correct 925 ms 219588 KB Output is correct
30 Execution timed out 1052 ms 353788 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 94832 KB Output is correct
2 Correct 123 ms 94592 KB Output is correct
3 Correct 195 ms 108632 KB Output is correct
4 Correct 180 ms 106624 KB Output is correct
5 Correct 307 ms 119008 KB Output is correct
6 Correct 303 ms 118912 KB Output is correct
7 Correct 243 ms 118836 KB Output is correct
8 Correct 246 ms 118912 KB Output is correct
9 Correct 632 ms 196212 KB Output is correct
10 Correct 226 ms 110204 KB Output is correct
11 Correct 367 ms 134012 KB Output is correct
12 Correct 97 ms 88520 KB Output is correct
13 Correct 79 ms 88652 KB Output is correct
14 Correct 110 ms 88600 KB Output is correct
15 Correct 90 ms 88516 KB Output is correct
16 Correct 82 ms 88516 KB Output is correct
17 Correct 84 ms 88516 KB Output is correct
18 Correct 107 ms 94824 KB Output is correct
19 Correct 127 ms 94660 KB Output is correct
20 Correct 109 ms 94632 KB Output is correct
21 Correct 108 ms 94836 KB Output is correct
22 Correct 623 ms 194288 KB Output is correct
23 Correct 744 ms 196796 KB Output is correct
24 Correct 819 ms 210944 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 138916 KB Output is correct
2 Correct 415 ms 150984 KB Output is correct
3 Correct 136 ms 94600 KB Output is correct
4 Correct 130 ms 94712 KB Output is correct
5 Execution timed out 1062 ms 333108 KB Time limit exceeded
6 Halted 0 ms 0 KB -