oj.uz

Submission #1077863

# Submission time Handle Problem Language Result Execution time Memory
1077863 2024-08-27T09:52:09 Z beaconmc Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 299816 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<ll, unordered_map<ll,ll>> 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:33: 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:9: note: in expansion of macro 'FOR'
   68 |         FOR(j,1,realheights[i].size()){
      |         ^~~
fish.cpp:67:12: warning: unused variable 'prev' [-Wunused-variable]
   67 |         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++)
......
   77 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:77:9: note: in expansion of macro 'FOR'
   77 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:86: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]
   86 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:84:20: warning: unused variable 'add' [-Wunused-variable]
   84 |                 ll add = 0;
      |                    ^~~
fish.cpp:135:16: warning: unused variable 'prev' [-Wunused-variable]
  135 |             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++)
......
  162 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:162:9: 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 198 ms 117828 KB Output is correct
2 Correct 233 ms 127396 KB Output is correct
3 Correct 126 ms 86088 KB Output is correct
4 Correct 94 ms 86100 KB Output is correct
5 Correct 838 ms 299816 KB Output is correct
6 Execution timed out 1096 ms 296008 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 83060 KB Output is correct
2 Correct 284 ms 137256 KB Output is correct
3 Correct 339 ms 145932 KB Output is correct
4 Correct 178 ms 117836 KB Output is correct
5 Correct 229 ms 127400 KB Output is correct
6 Correct 89 ms 83136 KB Output is correct
7 Correct 78 ms 83140 KB Output is correct
8 Correct 81 ms 83192 KB Output is correct
9 Correct 117 ms 83164 KB Output is correct
10 Correct 112 ms 86244 KB Output is correct
11 Correct 92 ms 86284 KB Output is correct
12 Correct 217 ms 127564 KB Output is correct
13 Correct 272 ms 139548 KB Output is correct
14 Correct 234 ms 122752 KB Output is correct
15 Correct 203 ms 114760 KB Output is correct
16 Correct 249 ms 122848 KB Output is correct
17 Correct 243 ms 129172 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 86212 KB Output is correct
2 Correct 106 ms 86184 KB Output is correct
3 Correct 195 ms 100548 KB Output is correct
4 Correct 180 ms 97440 KB Output is correct
5 Correct 264 ms 111068 KB Output is correct
6 Correct 287 ms 110280 KB Output is correct
7 Correct 262 ms 110920 KB Output is correct
8 Correct 264 ms 110908 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 83020 KB Output is correct
2 Correct 96 ms 83140 KB Output is correct
3 Correct 75 ms 83084 KB Output is correct
4 Correct 103 ms 83104 KB Output is correct
5 Correct 75 ms 83200 KB Output is correct
6 Correct 81 ms 83076 KB Output is correct
7 Correct 86 ms 82988 KB Output is correct
8 Correct 79 ms 83140 KB Output is correct
9 Correct 110 ms 83076 KB Output is correct
10 Correct 90 ms 83600 KB Output is correct
11 Correct 94 ms 83168 KB Output is correct
12 Correct 84 ms 83380 KB Output is correct
13 Correct 89 ms 83000 KB Output is correct
14 Correct 79 ms 83244 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 83020 KB Output is correct
2 Correct 96 ms 83140 KB Output is correct
3 Correct 75 ms 83084 KB Output is correct
4 Correct 103 ms 83104 KB Output is correct
5 Correct 75 ms 83200 KB Output is correct
6 Correct 81 ms 83076 KB Output is correct
7 Correct 86 ms 82988 KB Output is correct
8 Correct 79 ms 83140 KB Output is correct
9 Correct 110 ms 83076 KB Output is correct
10 Correct 90 ms 83600 KB Output is correct
11 Correct 94 ms 83168 KB Output is correct
12 Correct 84 ms 83380 KB Output is correct
13 Correct 89 ms 83000 KB Output is correct
14 Correct 79 ms 83244 KB Output is correct
15 Correct 98 ms 83176 KB Output is correct
16 Correct 94 ms 83828 KB Output is correct
17 Correct 161 ms 95620 KB Output is correct
18 Correct 148 ms 93380 KB Output is correct
19 Correct 127 ms 94664 KB Output is correct
20 Correct 116 ms 92684 KB Output is correct
21 Correct 134 ms 92512 KB Output is correct
22 Correct 153 ms 101940 KB Output is correct
23 Correct 99 ms 88564 KB Output is correct
24 Correct 146 ms 95176 KB Output is correct
25 Correct 72 ms 83556 KB Output is correct
26 Correct 117 ms 87236 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 83020 KB Output is correct
2 Correct 96 ms 83140 KB Output is correct
3 Correct 75 ms 83084 KB Output is correct
4 Correct 103 ms 83104 KB Output is correct
5 Correct 75 ms 83200 KB Output is correct
6 Correct 81 ms 83076 KB Output is correct
7 Correct 86 ms 82988 KB Output is correct
8 Correct 79 ms 83140 KB Output is correct
9 Correct 110 ms 83076 KB Output is correct
10 Correct 90 ms 83600 KB Output is correct
11 Correct 94 ms 83168 KB Output is correct
12 Correct 84 ms 83380 KB Output is correct
13 Correct 89 ms 83000 KB Output is correct
14 Correct 79 ms 83244 KB Output is correct
15 Correct 98 ms 83176 KB Output is correct
16 Correct 94 ms 83828 KB Output is correct
17 Correct 161 ms 95620 KB Output is correct
18 Correct 148 ms 93380 KB Output is correct
19 Correct 127 ms 94664 KB Output is correct
20 Correct 116 ms 92684 KB Output is correct
21 Correct 134 ms 92512 KB Output is correct
22 Correct 153 ms 101940 KB Output is correct
23 Correct 99 ms 88564 KB Output is correct
24 Correct 146 ms 95176 KB Output is correct
25 Correct 72 ms 83556 KB Output is correct
26 Correct 117 ms 87236 KB Output is correct
27 Correct 79 ms 85188 KB Output is correct
28 Correct 315 ms 133756 KB Output is correct
29 Correct 549 ms 187096 KB Output is correct
30 Correct 841 ms 272728 KB Output is correct
31 Correct 821 ms 264904 KB Output is correct
32 Correct 356 ms 145732 KB Output is correct
33 Correct 848 ms 285532 KB Output is correct
34 Correct 897 ms 285996 KB Output is correct
35 Correct 277 ms 131192 KB Output is correct
36 Correct 737 ms 228476 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 86212 KB Output is correct
2 Correct 106 ms 86184 KB Output is correct
3 Correct 195 ms 100548 KB Output is correct
4 Correct 180 ms 97440 KB Output is correct
5 Correct 264 ms 111068 KB Output is correct
6 Correct 287 ms 110280 KB Output is correct
7 Correct 262 ms 110920 KB Output is correct
8 Correct 264 ms 110908 KB Output is correct
9 Correct 453 ms 154624 KB Output is correct
10 Correct 216 ms 105156 KB Output is correct
11 Correct 461 ms 126992 KB Output is correct
12 Correct 84 ms 83076 KB Output is correct
13 Correct 124 ms 83168 KB Output is correct
14 Correct 74 ms 83080 KB Output is correct
15 Correct 136 ms 83144 KB Output is correct
16 Correct 141 ms 83144 KB Output is correct
17 Correct 70 ms 83000 KB Output is correct
18 Correct 99 ms 86216 KB Output is correct
19 Correct 93 ms 86212 KB Output is correct
20 Correct 136 ms 86204 KB Output is correct
21 Correct 129 ms 86184 KB Output is correct
22 Correct 575 ms 153192 KB Output is correct
23 Correct 580 ms 162248 KB Output is correct
24 Correct 624 ms 174040 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 117828 KB Output is correct
2 Correct 233 ms 127396 KB Output is correct
3 Correct 126 ms 86088 KB Output is correct
4 Correct 94 ms 86100 KB Output is correct
5 Correct 838 ms 299816 KB Output is correct
6 Execution timed out 1096 ms 296008 KB Time limit exceeded
7 Halted 0 ms 0 KB -