oj.uz

Submission #1070868

# Submission time Handle Problem Language Result Execution time Memory
1070868 2024-08-22T20:11:26 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 366272 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> weights[maxn];
 
vector<ll> p[maxn];
 
vector<array<ll,2>>  dp[maxn];
 
vector<ll> pref[maxn][2];
vector<ll> pref2[maxn][2];
vector<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::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++)
......
   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::vector<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::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++)
......
  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 129516 KB Output is correct
2 Correct 252 ms 141512 KB Output is correct
3 Correct 103 ms 87896 KB Output is correct
4 Correct 95 ms 87940 KB Output is correct
5 Execution timed out 1025 ms 366272 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 84820 KB Output is correct
2 Correct 388 ms 150724 KB Output is correct
3 Correct 432 ms 160824 KB Output is correct
4 Correct 219 ms 129608 KB Output is correct
5 Correct 250 ms 141336 KB Output is correct
6 Correct 68 ms 84820 KB Output is correct
7 Correct 65 ms 84732 KB Output is correct
8 Correct 64 ms 84812 KB Output is correct
9 Correct 83 ms 84816 KB Output is correct
10 Correct 94 ms 87900 KB Output is correct
11 Correct 81 ms 87888 KB Output is correct
12 Correct 254 ms 142980 KB Output is correct
13 Correct 331 ms 158372 KB Output is correct
14 Correct 263 ms 136428 KB Output is correct
15 Correct 218 ms 123252 KB Output is correct
16 Correct 281 ms 136360 KB Output is correct
17 Correct 282 ms 144088 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 87892 KB Output is correct
2 Correct 100 ms 88020 KB Output is correct
3 Correct 133 ms 95520 KB Output is correct
4 Correct 131 ms 94292 KB Output is correct
5 Correct 171 ms 101228 KB Output is correct
6 Correct 168 ms 101200 KB Output is correct
7 Correct 198 ms 101204 KB Output is correct
8 Correct 168 ms 101200 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 84820 KB Output is correct
2 Correct 83 ms 84816 KB Output is correct
3 Correct 80 ms 84816 KB Output is correct
4 Correct 72 ms 84820 KB Output is correct
5 Correct 84 ms 84820 KB Output is correct
6 Correct 64 ms 84912 KB Output is correct
7 Correct 78 ms 84772 KB Output is correct
8 Correct 63 ms 84904 KB Output is correct
9 Correct 75 ms 85076 KB Output is correct
10 Correct 71 ms 85328 KB Output is correct
11 Correct 61 ms 85072 KB Output is correct
12 Correct 69 ms 85152 KB Output is correct
13 Correct 64 ms 84816 KB Output is correct
14 Correct 63 ms 85080 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 84820 KB Output is correct
2 Correct 83 ms 84816 KB Output is correct
3 Correct 80 ms 84816 KB Output is correct
4 Correct 72 ms 84820 KB Output is correct
5 Correct 84 ms 84820 KB Output is correct
6 Correct 64 ms 84912 KB Output is correct
7 Correct 78 ms 84772 KB Output is correct
8 Correct 63 ms 84904 KB Output is correct
9 Correct 75 ms 85076 KB Output is correct
10 Correct 71 ms 85328 KB Output is correct
11 Correct 61 ms 85072 KB Output is correct
12 Correct 69 ms 85152 KB Output is correct
13 Correct 64 ms 84816 KB Output is correct
14 Correct 63 ms 85080 KB Output is correct
15 Correct 81 ms 85076 KB Output is correct
16 Correct 79 ms 85584 KB Output is correct
17 Correct 151 ms 98032 KB Output is correct
18 Correct 136 ms 95316 KB Output is correct
19 Correct 150 ms 97108 KB Output is correct
20 Correct 140 ms 94308 KB Output is correct
21 Correct 119 ms 93820 KB Output is correct
22 Correct 179 ms 102992 KB Output is correct
23 Correct 109 ms 91816 KB Output is correct
24 Correct 150 ms 99652 KB Output is correct
25 Correct 70 ms 85576 KB Output is correct
26 Correct 106 ms 89940 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 84820 KB Output is correct
2 Correct 83 ms 84816 KB Output is correct
3 Correct 80 ms 84816 KB Output is correct
4 Correct 72 ms 84820 KB Output is correct
5 Correct 84 ms 84820 KB Output is correct
6 Correct 64 ms 84912 KB Output is correct
7 Correct 78 ms 84772 KB Output is correct
8 Correct 63 ms 84904 KB Output is correct
9 Correct 75 ms 85076 KB Output is correct
10 Correct 71 ms 85328 KB Output is correct
11 Correct 61 ms 85072 KB Output is correct
12 Correct 69 ms 85152 KB Output is correct
13 Correct 64 ms 84816 KB Output is correct
14 Correct 63 ms 85080 KB Output is correct
15 Correct 81 ms 85076 KB Output is correct
16 Correct 79 ms 85584 KB Output is correct
17 Correct 151 ms 98032 KB Output is correct
18 Correct 136 ms 95316 KB Output is correct
19 Correct 150 ms 97108 KB Output is correct
20 Correct 140 ms 94308 KB Output is correct
21 Correct 119 ms 93820 KB Output is correct
22 Correct 179 ms 102992 KB Output is correct
23 Correct 109 ms 91816 KB Output is correct
24 Correct 150 ms 99652 KB Output is correct
25 Correct 70 ms 85576 KB Output is correct
26 Correct 106 ms 89940 KB Output is correct
27 Correct 75 ms 87380 KB Output is correct
28 Correct 408 ms 137552 KB Output is correct
29 Correct 799 ms 204984 KB Output is correct
30 Execution timed out 1054 ms 332116 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 87892 KB Output is correct
2 Correct 100 ms 88020 KB Output is correct
3 Correct 133 ms 95520 KB Output is correct
4 Correct 131 ms 94292 KB Output is correct
5 Correct 171 ms 101228 KB Output is correct
6 Correct 168 ms 101200 KB Output is correct
7 Correct 198 ms 101204 KB Output is correct
8 Correct 168 ms 101200 KB Output is correct
9 Correct 364 ms 166992 KB Output is correct
10 Correct 153 ms 104480 KB Output is correct
11 Correct 265 ms 124088 KB Output is correct
12 Correct 64 ms 84816 KB Output is correct
13 Correct 61 ms 84820 KB Output is correct
14 Correct 66 ms 84964 KB Output is correct
15 Correct 65 ms 84816 KB Output is correct
16 Correct 69 ms 84944 KB Output is correct
17 Correct 72 ms 84820 KB Output is correct
18 Correct 91 ms 87892 KB Output is correct
19 Correct 77 ms 87868 KB Output is correct
20 Correct 80 ms 87904 KB Output is correct
21 Correct 90 ms 87888 KB Output is correct
22 Correct 370 ms 170528 KB Output is correct
23 Correct 438 ms 171560 KB Output is correct
24 Correct 551 ms 188500 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 129516 KB Output is correct
2 Correct 252 ms 141512 KB Output is correct
3 Correct 103 ms 87896 KB Output is correct
4 Correct 95 ms 87940 KB Output is correct
5 Execution timed out 1025 ms 366272 KB Time limit exceeded
6 Halted 0 ms 0 KB -