oj.uz

Submission #1070901

# Submission time Handle Problem Language Result Execution time Memory
1070901 2024-08-22T20:34:32 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 306092 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]);
        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){
                if (weights[i].count(realheights[i][j])) tempadd += weights[i][realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                if (weights[i-1].count(realheights[i][j]))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++)
......
   63 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:63:9: note: in expansion of macro 'FOR'
   63 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:62:12: warning: unused variable 'prev' [-Wunused-variable]
   62 |         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++)
......
   72 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:72:9: note: in expansion of macro 'FOR'
   72 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:81: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]
   81 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:79:20: warning: unused variable 'add' [-Wunused-variable]
   79 |                 ll add = 0;
      |                    ^~~
fish.cpp:129:16: warning: unused variable 'prev' [-Wunused-variable]
  129 |             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++)
......
  156 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:156:9: note: in expansion of macro 'FOR'
  156 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 135528 KB Output is correct
2 Correct 258 ms 146804 KB Output is correct
3 Correct 80 ms 93524 KB Output is correct
4 Correct 104 ms 93524 KB Output is correct
5 Execution timed out 1014 ms 306092 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 93524 KB Output is correct
2 Correct 381 ms 156420 KB Output is correct
3 Correct 457 ms 166200 KB Output is correct
4 Correct 229 ms 135264 KB Output is correct
5 Correct 272 ms 146888 KB Output is correct
6 Correct 78 ms 93520 KB Output is correct
7 Correct 79 ms 93408 KB Output is correct
8 Correct 80 ms 93572 KB Output is correct
9 Correct 87 ms 93544 KB Output is correct
10 Correct 87 ms 93528 KB Output is correct
11 Correct 86 ms 93524 KB Output is correct
12 Correct 276 ms 148960 KB Output is correct
13 Correct 354 ms 164036 KB Output is correct
14 Correct 278 ms 142180 KB Output is correct
15 Correct 245 ms 128624 KB Output is correct
16 Correct 273 ms 142316 KB Output is correct
17 Correct 314 ms 149644 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 93524 KB Output is correct
2 Correct 82 ms 93520 KB Output is correct
3 Correct 140 ms 107856 KB Output is correct
4 Correct 129 ms 105044 KB Output is correct
5 Correct 183 ms 117804 KB Output is correct
6 Correct 193 ms 117840 KB Output is correct
7 Correct 188 ms 117840 KB Output is correct
8 Correct 178 ms 117836 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 93524 KB Output is correct
2 Correct 74 ms 93520 KB Output is correct
3 Correct 81 ms 93348 KB Output is correct
4 Correct 76 ms 93520 KB Output is correct
5 Correct 74 ms 93376 KB Output is correct
6 Correct 72 ms 93384 KB Output is correct
7 Correct 85 ms 93380 KB Output is correct
8 Correct 83 ms 93520 KB Output is correct
9 Correct 98 ms 93520 KB Output is correct
10 Correct 85 ms 93780 KB Output is correct
11 Correct 86 ms 93536 KB Output is correct
12 Correct 92 ms 93904 KB Output is correct
13 Correct 83 ms 93384 KB Output is correct
14 Correct 84 ms 93776 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 93524 KB Output is correct
2 Correct 74 ms 93520 KB Output is correct
3 Correct 81 ms 93348 KB Output is correct
4 Correct 76 ms 93520 KB Output is correct
5 Correct 74 ms 93376 KB Output is correct
6 Correct 72 ms 93384 KB Output is correct
7 Correct 85 ms 93380 KB Output is correct
8 Correct 83 ms 93520 KB Output is correct
9 Correct 98 ms 93520 KB Output is correct
10 Correct 85 ms 93780 KB Output is correct
11 Correct 86 ms 93536 KB Output is correct
12 Correct 92 ms 93904 KB Output is correct
13 Correct 83 ms 93384 KB Output is correct
14 Correct 84 ms 93776 KB Output is correct
15 Correct 85 ms 93524 KB Output is correct
16 Correct 90 ms 93944 KB Output is correct
17 Correct 145 ms 105808 KB Output is correct
18 Correct 148 ms 103616 KB Output is correct
19 Correct 141 ms 104788 KB Output is correct
20 Correct 128 ms 102740 KB Output is correct
21 Correct 143 ms 102548 KB Output is correct
22 Correct 186 ms 111440 KB Output is correct
23 Correct 114 ms 98896 KB Output is correct
24 Correct 155 ms 106124 KB Output is correct
25 Correct 83 ms 94032 KB Output is correct
26 Correct 108 ms 97844 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 93524 KB Output is correct
2 Correct 74 ms 93520 KB Output is correct
3 Correct 81 ms 93348 KB Output is correct
4 Correct 76 ms 93520 KB Output is correct
5 Correct 74 ms 93376 KB Output is correct
6 Correct 72 ms 93384 KB Output is correct
7 Correct 85 ms 93380 KB Output is correct
8 Correct 83 ms 93520 KB Output is correct
9 Correct 98 ms 93520 KB Output is correct
10 Correct 85 ms 93780 KB Output is correct
11 Correct 86 ms 93536 KB Output is correct
12 Correct 92 ms 93904 KB Output is correct
13 Correct 83 ms 93384 KB Output is correct
14 Correct 84 ms 93776 KB Output is correct
15 Correct 85 ms 93524 KB Output is correct
16 Correct 90 ms 93944 KB Output is correct
17 Correct 145 ms 105808 KB Output is correct
18 Correct 148 ms 103616 KB Output is correct
19 Correct 141 ms 104788 KB Output is correct
20 Correct 128 ms 102740 KB Output is correct
21 Correct 143 ms 102548 KB Output is correct
22 Correct 186 ms 111440 KB Output is correct
23 Correct 114 ms 98896 KB Output is correct
24 Correct 155 ms 106124 KB Output is correct
25 Correct 83 ms 94032 KB Output is correct
26 Correct 108 ms 97844 KB Output is correct
27 Correct 103 ms 95312 KB Output is correct
28 Correct 391 ms 145492 KB Output is correct
29 Correct 811 ms 197416 KB Output is correct
30 Execution timed out 1079 ms 289376 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 93524 KB Output is correct
2 Correct 82 ms 93520 KB Output is correct
3 Correct 140 ms 107856 KB Output is correct
4 Correct 129 ms 105044 KB Output is correct
5 Correct 183 ms 117804 KB Output is correct
6 Correct 193 ms 117840 KB Output is correct
7 Correct 188 ms 117840 KB Output is correct
8 Correct 178 ms 117836 KB Output is correct
9 Correct 413 ms 160084 KB Output is correct
10 Correct 179 ms 111444 KB Output is correct
11 Correct 330 ms 129360 KB Output is correct
12 Correct 93 ms 93520 KB Output is correct
13 Correct 82 ms 93524 KB Output is correct
14 Correct 94 ms 93440 KB Output is correct
15 Correct 92 ms 93444 KB Output is correct
16 Correct 87 ms 93568 KB Output is correct
17 Correct 79 ms 93468 KB Output is correct
18 Correct 84 ms 93520 KB Output is correct
19 Correct 91 ms 93484 KB Output is correct
20 Correct 88 ms 93520 KB Output is correct
21 Correct 88 ms 93412 KB Output is correct
22 Correct 393 ms 162388 KB Output is correct
23 Correct 552 ms 172372 KB Output is correct
24 Correct 560 ms 180048 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 135528 KB Output is correct
2 Correct 258 ms 146804 KB Output is correct
3 Correct 80 ms 93524 KB Output is correct
4 Correct 104 ms 93524 KB Output is correct
5 Execution timed out 1014 ms 306092 KB Time limit exceeded
6 Halted 0 ms 0 KB -