oj.uz

Submission #1070896

# Submission time Handle Problem Language Result Execution time Memory
1070896 2024-08-22T20:32:39 Z beaconmc Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 357552 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]);
        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){
                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++)
......
   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::__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++)
......
   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::__cxx11::basic_string<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::__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++)
......
  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 231 ms 135272 KB Output is correct
2 Correct 302 ms 146836 KB Output is correct
3 Correct 78 ms 93340 KB Output is correct
4 Correct 77 ms 93520 KB Output is correct
5 Execution timed out 1098 ms 357552 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 93392 KB Output is correct
2 Correct 426 ms 156544 KB Output is correct
3 Correct 499 ms 166200 KB Output is correct
4 Correct 253 ms 135272 KB Output is correct
5 Correct 284 ms 146884 KB Output is correct
6 Correct 82 ms 93372 KB Output is correct
7 Correct 95 ms 93484 KB Output is correct
8 Correct 118 ms 93520 KB Output is correct
9 Correct 85 ms 93524 KB Output is correct
10 Correct 115 ms 93372 KB Output is correct
11 Correct 106 ms 93440 KB Output is correct
12 Correct 290 ms 149012 KB Output is correct
13 Correct 409 ms 164036 KB Output is correct
14 Correct 324 ms 142312 KB Output is correct
15 Correct 276 ms 128624 KB Output is correct
16 Correct 293 ms 142312 KB Output is correct
17 Correct 307 ms 149560 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 93564 KB Output is correct
2 Correct 75 ms 93368 KB Output is correct
3 Correct 138 ms 107860 KB Output is correct
4 Correct 125 ms 105176 KB Output is correct
5 Correct 197 ms 117840 KB Output is correct
6 Correct 191 ms 117844 KB Output is correct
7 Correct 201 ms 117844 KB Output is correct
8 Correct 209 ms 117840 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 93520 KB Output is correct
2 Correct 72 ms 93576 KB Output is correct
3 Correct 69 ms 93520 KB Output is correct
4 Correct 70 ms 93532 KB Output is correct
5 Correct 63 ms 93468 KB Output is correct
6 Correct 75 ms 93496 KB Output is correct
7 Correct 65 ms 93524 KB Output is correct
8 Correct 111 ms 93520 KB Output is correct
9 Correct 82 ms 93452 KB Output is correct
10 Correct 73 ms 93776 KB Output is correct
11 Correct 78 ms 93544 KB Output is correct
12 Correct 77 ms 93772 KB Output is correct
13 Correct 72 ms 93524 KB Output is correct
14 Correct 87 ms 93780 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 93520 KB Output is correct
2 Correct 72 ms 93576 KB Output is correct
3 Correct 69 ms 93520 KB Output is correct
4 Correct 70 ms 93532 KB Output is correct
5 Correct 63 ms 93468 KB Output is correct
6 Correct 75 ms 93496 KB Output is correct
7 Correct 65 ms 93524 KB Output is correct
8 Correct 111 ms 93520 KB Output is correct
9 Correct 82 ms 93452 KB Output is correct
10 Correct 73 ms 93776 KB Output is correct
11 Correct 78 ms 93544 KB Output is correct
12 Correct 77 ms 93772 KB Output is correct
13 Correct 72 ms 93524 KB Output is correct
14 Correct 87 ms 93780 KB Output is correct
15 Correct 98 ms 93820 KB Output is correct
16 Correct 95 ms 94036 KB Output is correct
17 Correct 148 ms 106324 KB Output is correct
18 Correct 139 ms 104016 KB Output is correct
19 Correct 154 ms 105556 KB Output is correct
20 Correct 125 ms 102740 KB Output is correct
21 Correct 146 ms 102480 KB Output is correct
22 Correct 206 ms 111416 KB Output is correct
23 Correct 113 ms 99920 KB Output is correct
24 Correct 140 ms 108112 KB Output is correct
25 Correct 70 ms 94128 KB Output is correct
26 Correct 116 ms 98356 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 93520 KB Output is correct
2 Correct 72 ms 93576 KB Output is correct
3 Correct 69 ms 93520 KB Output is correct
4 Correct 70 ms 93532 KB Output is correct
5 Correct 63 ms 93468 KB Output is correct
6 Correct 75 ms 93496 KB Output is correct
7 Correct 65 ms 93524 KB Output is correct
8 Correct 111 ms 93520 KB Output is correct
9 Correct 82 ms 93452 KB Output is correct
10 Correct 73 ms 93776 KB Output is correct
11 Correct 78 ms 93544 KB Output is correct
12 Correct 77 ms 93772 KB Output is correct
13 Correct 72 ms 93524 KB Output is correct
14 Correct 87 ms 93780 KB Output is correct
15 Correct 98 ms 93820 KB Output is correct
16 Correct 95 ms 94036 KB Output is correct
17 Correct 148 ms 106324 KB Output is correct
18 Correct 139 ms 104016 KB Output is correct
19 Correct 154 ms 105556 KB Output is correct
20 Correct 125 ms 102740 KB Output is correct
21 Correct 146 ms 102480 KB Output is correct
22 Correct 206 ms 111416 KB Output is correct
23 Correct 113 ms 99920 KB Output is correct
24 Correct 140 ms 108112 KB Output is correct
25 Correct 70 ms 94128 KB Output is correct
26 Correct 116 ms 98356 KB Output is correct
27 Correct 74 ms 96080 KB Output is correct
28 Correct 423 ms 146004 KB Output is correct
29 Correct 825 ms 210004 KB Output is correct
30 Execution timed out 1058 ms 325712 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 93564 KB Output is correct
2 Correct 75 ms 93368 KB Output is correct
3 Correct 138 ms 107860 KB Output is correct
4 Correct 125 ms 105176 KB Output is correct
5 Correct 197 ms 117840 KB Output is correct
6 Correct 191 ms 117844 KB Output is correct
7 Correct 201 ms 117844 KB Output is correct
8 Correct 209 ms 117840 KB Output is correct
9 Correct 356 ms 180304 KB Output is correct
10 Correct 177 ms 111440 KB Output is correct
11 Correct 287 ms 129360 KB Output is correct
12 Correct 77 ms 93516 KB Output is correct
13 Correct 66 ms 93524 KB Output is correct
14 Correct 84 ms 93516 KB Output is correct
15 Correct 72 ms 93396 KB Output is correct
16 Correct 91 ms 93520 KB Output is correct
17 Correct 70 ms 93520 KB Output is correct
18 Correct 76 ms 93520 KB Output is correct
19 Correct 90 ms 93524 KB Output is correct
20 Correct 77 ms 93392 KB Output is correct
21 Correct 86 ms 93520 KB Output is correct
22 Correct 429 ms 178512 KB Output is correct
23 Correct 479 ms 181332 KB Output is correct
24 Correct 551 ms 196372 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 135272 KB Output is correct
2 Correct 302 ms 146836 KB Output is correct
3 Correct 78 ms 93340 KB Output is correct
4 Correct 77 ms 93520 KB Output is correct
5 Execution timed out 1098 ms 357552 KB Time limit exceeded
6 Halted 0 ms 0 KB -