oj.uz

Submission #1070802

# Submission time Handle Problem Language Result Execution time Memory
1070802 2024-08-22T18:44:16 Z beaconmc Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 437172 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> fish[maxn];
    unordered_map<ll,ll> weights[maxn];
     
    unordered_map<ll,ll> p[maxn];
     
    vector<array<ll,2>>  dp[maxn];
     
    unordered_map<ll,ll> pref[maxn][2];
    unordered_map<ll,ll> pref2[maxn][2];
    unordered_map<ll,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]++;
            fish[X[i]][Y[i]] = 1;
            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){
            p[i][0] = 0;
            ll prev = 0;
            for (auto j : heights[i]){
                if (j==0) continue;
                p[i][j] = p[i][prev] + weights[i][j];
                prev = j;
            }
        }
        FOR(i,0,maxn){
            for (auto k : heights[i]) realheights[i].push_back(k);
        }
        FOR(i,0,maxn){
            dp[i].resize(heights[i].size());
        }
     
        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 up = *upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]);
                        ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                        temp = max(temp, suff[i-1][0][up] - p[i-1][down]);
                        temp = max(temp, suff[i-1][1][up] - 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(), realheights[i][X]));
                        ll down2 = *(--upper_bound(realheights[i-2].begin(), realheights[i-2].end(), realheights[i][X]));
     
                        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][realheights[i][j]] = dp[i][j][k]+tempadd;
                }
     
                FOR(j,0,sz){
                    tempadd2 -= weights[i-1][realheights[i][j]];
                    pref[i][k][realheights[i][j]] = dp[i][j][k] + tempadd2;
                    pref2[i][k][realheights[i][j]] = dp[i][j][k];
                }
                ll prev = 0;
                FOR(j,1,sz){
                    pref[i][k][realheights[i][j]] = max(pref[i][k][realheights[i][j]], pref[i][k][prev]);
                    pref2[i][k][realheights[i][j]] = max(pref2[i][k][realheights[i][j]], pref2[i][k][prev]);
                    prev = realheights[i][j];
                }
                prev = realheights[i][sz-1];
                FORNEG(j,sz-2,-1){
                    suff[i][k][realheights[i][j]] = max(suff[i][k][realheights[i][j]], suff[i][k][prev]);
     
                    prev = realheights[i][j];
                }
     
            }
            // 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:37: 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++)
......
   65 |             FOR(X,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:65:13: note: in expansion of macro 'FOR'
   65 |             FOR(X,0,dp[i].size()){
      |             ^~~
fish.cpp:74:30: 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]
   74 |                         if (X==dp[i].size()-1) continue;
      |                             ~^~~~~~~~~~~~~~~~
fish.cpp:72:24: warning: unused variable 'add' [-Wunused-variable]
   72 |                     ll add = 0;
      |                        ^~~
fish.cpp:66:20: warning: unused variable 'j' [-Wunused-variable]
   66 |                 ll j = realheights[i][X];
      |                    ^
fish.cpp:9:37: 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++)
......
  148 |             FOR(j,0,dp[i].size()){
      |                 ~~~~~~~~~~~~~~~~     
fish.cpp:148:13: note: in expansion of macro 'FOR'
  148 |             FOR(j,0,dp[i].size()){
      |             ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 283112 KB Output is correct
2 Correct 530 ms 322620 KB Output is correct
3 Correct 212 ms 214100 KB Output is correct
4 Correct 337 ms 213872 KB Output is correct
5 Execution timed out 1063 ms 338864 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 107476 KB Output is correct
2 Correct 818 ms 338364 KB Output is correct
3 Execution timed out 1006 ms 372424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 214008 KB Output is correct
2 Correct 322 ms 214024 KB Output is correct
3 Correct 286 ms 231768 KB Output is correct
4 Correct 392 ms 236404 KB Output is correct
5 Correct 404 ms 263344 KB Output is correct
6 Correct 374 ms 263248 KB Output is correct
7 Correct 410 ms 263352 KB Output is correct
8 Correct 386 ms 263248 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 107604 KB Output is correct
2 Correct 67 ms 107680 KB Output is correct
3 Correct 63 ms 107660 KB Output is correct
4 Correct 103 ms 107660 KB Output is correct
5 Correct 67 ms 107600 KB Output is correct
6 Correct 58 ms 107600 KB Output is correct
7 Correct 65 ms 107536 KB Output is correct
8 Correct 96 ms 107640 KB Output is correct
9 Correct 72 ms 107860 KB Output is correct
10 Correct 101 ms 108784 KB Output is correct
11 Correct 66 ms 108116 KB Output is correct
12 Correct 67 ms 108720 KB Output is correct
13 Correct 76 ms 107604 KB Output is correct
14 Correct 69 ms 108376 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 107604 KB Output is correct
2 Correct 67 ms 107680 KB Output is correct
3 Correct 63 ms 107660 KB Output is correct
4 Correct 103 ms 107660 KB Output is correct
5 Correct 67 ms 107600 KB Output is correct
6 Correct 58 ms 107600 KB Output is correct
7 Correct 65 ms 107536 KB Output is correct
8 Correct 96 ms 107640 KB Output is correct
9 Correct 72 ms 107860 KB Output is correct
10 Correct 101 ms 108784 KB Output is correct
11 Correct 66 ms 108116 KB Output is correct
12 Correct 67 ms 108720 KB Output is correct
13 Correct 76 ms 107604 KB Output is correct
14 Correct 69 ms 108376 KB Output is correct
15 Correct 79 ms 108400 KB Output is correct
16 Correct 105 ms 109140 KB Output is correct
17 Correct 197 ms 140100 KB Output is correct
18 Correct 245 ms 134220 KB Output is correct
19 Correct 176 ms 138320 KB Output is correct
20 Correct 175 ms 131152 KB Output is correct
21 Correct 173 ms 130372 KB Output is correct
22 Correct 278 ms 153428 KB Output is correct
23 Correct 134 ms 123984 KB Output is correct
24 Correct 216 ms 144468 KB Output is correct
25 Correct 64 ms 109344 KB Output is correct
26 Correct 140 ms 119824 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 107604 KB Output is correct
2 Correct 67 ms 107680 KB Output is correct
3 Correct 63 ms 107660 KB Output is correct
4 Correct 103 ms 107660 KB Output is correct
5 Correct 67 ms 107600 KB Output is correct
6 Correct 58 ms 107600 KB Output is correct
7 Correct 65 ms 107536 KB Output is correct
8 Correct 96 ms 107640 KB Output is correct
9 Correct 72 ms 107860 KB Output is correct
10 Correct 101 ms 108784 KB Output is correct
11 Correct 66 ms 108116 KB Output is correct
12 Correct 67 ms 108720 KB Output is correct
13 Correct 76 ms 107604 KB Output is correct
14 Correct 69 ms 108376 KB Output is correct
15 Correct 79 ms 108400 KB Output is correct
16 Correct 105 ms 109140 KB Output is correct
17 Correct 197 ms 140100 KB Output is correct
18 Correct 245 ms 134220 KB Output is correct
19 Correct 176 ms 138320 KB Output is correct
20 Correct 175 ms 131152 KB Output is correct
21 Correct 173 ms 130372 KB Output is correct
22 Correct 278 ms 153428 KB Output is correct
23 Correct 134 ms 123984 KB Output is correct
24 Correct 216 ms 144468 KB Output is correct
25 Correct 64 ms 109344 KB Output is correct
26 Correct 140 ms 119824 KB Output is correct
27 Correct 81 ms 116048 KB Output is correct
28 Correct 798 ms 238932 KB Output is correct
29 Execution timed out 1068 ms 298036 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 214008 KB Output is correct
2 Correct 322 ms 214024 KB Output is correct
3 Correct 286 ms 231768 KB Output is correct
4 Correct 392 ms 236404 KB Output is correct
5 Correct 404 ms 263344 KB Output is correct
6 Correct 374 ms 263248 KB Output is correct
7 Correct 410 ms 263352 KB Output is correct
8 Correct 386 ms 263248 KB Output is correct
9 Correct 820 ms 394696 KB Output is correct
10 Correct 401 ms 203856 KB Output is correct
11 Correct 718 ms 300112 KB Output is correct
12 Correct 84 ms 107600 KB Output is correct
13 Correct 66 ms 107572 KB Output is correct
14 Correct 65 ms 107596 KB Output is correct
15 Correct 82 ms 107480 KB Output is correct
16 Correct 63 ms 107600 KB Output is correct
17 Correct 90 ms 107600 KB Output is correct
18 Correct 257 ms 214096 KB Output is correct
19 Correct 195 ms 213876 KB Output is correct
20 Correct 203 ms 214164 KB Output is correct
21 Correct 202 ms 214100 KB Output is correct
22 Correct 852 ms 391760 KB Output is correct
23 Correct 962 ms 400904 KB Output is correct
24 Execution timed out 1072 ms 437172 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 283112 KB Output is correct
2 Correct 530 ms 322620 KB Output is correct
3 Correct 212 ms 214100 KB Output is correct
4 Correct 337 ms 213872 KB Output is correct
5 Execution timed out 1063 ms 338864 KB Time limit exceeded
6 Halted 0 ms 0 KB -