oj.uz

Submission #1070874

# Submission time Handle Problem Language Result Execution time Memory
1070874 2024-08-22T20:17:10 Z beaconmc Catfish Farm (IOI22_fish) C++17
41 / 100
 1000 ms 348612 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;
 
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]*1000000+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*1000000+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*1000000+realheights[i][j]];
                suff[i][k][j] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[(i-1)*1000000+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 325 ms 125508 KB Output is correct
2 Correct 395 ms 135076 KB Output is correct
3 Correct 78 ms 83396 KB Output is correct
4 Correct 82 ms 83400 KB Output is correct
5 Execution timed out 1101 ms 348612 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78692 KB Output is correct
2 Correct 550 ms 143672 KB Output is correct
3 Correct 654 ms 153028 KB Output is correct
4 Correct 345 ms 125368 KB Output is correct
5 Correct 383 ms 135112 KB Output is correct
6 Correct 65 ms 78688 KB Output is correct
7 Correct 62 ms 78692 KB Output is correct
8 Correct 63 ms 78512 KB Output is correct
9 Correct 88 ms 78476 KB Output is correct
10 Correct 104 ms 83400 KB Output is correct
11 Correct 106 ms 83396 KB Output is correct
12 Correct 391 ms 138292 KB Output is correct
13 Correct 487 ms 150840 KB Output is correct
14 Correct 454 ms 131904 KB Output is correct
15 Correct 333 ms 119748 KB Output is correct
16 Correct 375 ms 131772 KB Output is correct
17 Correct 467 ms 137396 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 83392 KB Output is correct
2 Incorrect 82 ms 83400 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 78688 KB Output is correct
2 Correct 61 ms 78688 KB Output is correct
3 Correct 60 ms 78568 KB Output is correct
4 Correct 79 ms 78680 KB Output is correct
5 Correct 64 ms 78656 KB Output is correct
6 Correct 59 ms 78548 KB Output is correct
7 Correct 62 ms 78692 KB Output is correct
8 Correct 60 ms 78660 KB Output is correct
9 Correct 61 ms 78632 KB Output is correct
10 Correct 64 ms 78944 KB Output is correct
11 Correct 62 ms 78688 KB Output is correct
12 Correct 62 ms 79036 KB Output is correct
13 Correct 61 ms 78692 KB Output is correct
14 Correct 61 ms 78688 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 78688 KB Output is correct
2 Correct 61 ms 78688 KB Output is correct
3 Correct 60 ms 78568 KB Output is correct
4 Correct 79 ms 78680 KB Output is correct
5 Correct 64 ms 78656 KB Output is correct
6 Correct 59 ms 78548 KB Output is correct
7 Correct 62 ms 78692 KB Output is correct
8 Correct 60 ms 78660 KB Output is correct
9 Correct 61 ms 78632 KB Output is correct
10 Correct 64 ms 78944 KB Output is correct
11 Correct 62 ms 78688 KB Output is correct
12 Correct 62 ms 79036 KB Output is correct
13 Correct 61 ms 78692 KB Output is correct
14 Correct 61 ms 78688 KB Output is correct
15 Correct 63 ms 78896 KB Output is correct
16 Correct 70 ms 79204 KB Output is correct
17 Correct 142 ms 90556 KB Output is correct
18 Correct 138 ms 88004 KB Output is correct
19 Correct 155 ms 89828 KB Output is correct
20 Correct 156 ms 87360 KB Output is correct
21 Correct 126 ms 86756 KB Output is correct
22 Correct 207 ms 97476 KB Output is correct
23 Correct 97 ms 84764 KB Output is correct
24 Correct 139 ms 94404 KB Output is correct
25 Correct 61 ms 79048 KB Output is correct
26 Correct 90 ms 83172 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 78688 KB Output is correct
2 Correct 61 ms 78688 KB Output is correct
3 Correct 60 ms 78568 KB Output is correct
4 Correct 79 ms 78680 KB Output is correct
5 Correct 64 ms 78656 KB Output is correct
6 Correct 59 ms 78548 KB Output is correct
7 Correct 62 ms 78692 KB Output is correct
8 Correct 60 ms 78660 KB Output is correct
9 Correct 61 ms 78632 KB Output is correct
10 Correct 64 ms 78944 KB Output is correct
11 Correct 62 ms 78688 KB Output is correct
12 Correct 62 ms 79036 KB Output is correct
13 Correct 61 ms 78692 KB Output is correct
14 Correct 61 ms 78688 KB Output is correct
15 Correct 63 ms 78896 KB Output is correct
16 Correct 70 ms 79204 KB Output is correct
17 Correct 142 ms 90556 KB Output is correct
18 Correct 138 ms 88004 KB Output is correct
19 Correct 155 ms 89828 KB Output is correct
20 Correct 156 ms 87360 KB Output is correct
21 Correct 126 ms 86756 KB Output is correct
22 Correct 207 ms 97476 KB Output is correct
23 Correct 97 ms 84764 KB Output is correct
24 Correct 139 ms 94404 KB Output is correct
25 Correct 61 ms 79048 KB Output is correct
26 Correct 90 ms 83172 KB Output is correct
27 Incorrect 70 ms 81292 KB 1st lines differ - on the 1st token, expected: '2999', found: '2148'
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 83392 KB Output is correct
2 Incorrect 82 ms 83400 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 125508 KB Output is correct
2 Correct 395 ms 135076 KB Output is correct
3 Correct 78 ms 83396 KB Output is correct
4 Correct 82 ms 83400 KB Output is correct
5 Execution timed out 1101 ms 348612 KB Time limit exceeded
6 Halted 0 ms 0 KB -