oj.uz

Submission #1070872

# Submission time Handle Problem Language Result Execution time Memory
1070872 2024-08-22T20:15:47 Z beaconmc Catfish Farm (IOI22_fish) C++17
41 / 100
 1000 ms 350436 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) {
    weights.reserve(524288);
 
    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++)
......
   65 |         FOR(j,1,heights[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~~~
fish.cpp:65:9: note: in expansion of macro 'FOR'
   65 |         FOR(j,1,heights[i].size()){
      |         ^~~
fish.cpp:64:12: warning: unused variable 'prev' [-Wunused-variable]
   64 |         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++)
......
   74 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:74:9: note: in expansion of macro 'FOR'
   74 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:83: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]
   83 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:81:20: warning: unused variable 'add' [-Wunused-variable]
   81 |                 ll add = 0;
      |                    ^~~
fish.cpp:131:16: warning: unused variable 'prev' [-Wunused-variable]
  131 |             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++)
......
  158 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:158:9: note: in expansion of macro 'FOR'
  158 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 124096 KB Output is correct
2 Correct 288 ms 133828 KB Output is correct
3 Correct 87 ms 84556 KB Output is correct
4 Correct 100 ms 84560 KB Output is correct
5 Execution timed out 1093 ms 350436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 81356 KB Output is correct
2 Correct 478 ms 142488 KB Output is correct
3 Correct 551 ms 159828 KB Output is correct
4 Correct 251 ms 123992 KB Output is correct
5 Correct 325 ms 133988 KB Output is correct
6 Correct 69 ms 81492 KB Output is correct
7 Correct 67 ms 81488 KB Output is correct
8 Correct 64 ms 81488 KB Output is correct
9 Correct 87 ms 81492 KB Output is correct
10 Correct 80 ms 84564 KB Output is correct
11 Correct 86 ms 84560 KB Output is correct
12 Correct 363 ms 137040 KB Output is correct
13 Correct 444 ms 157504 KB Output is correct
14 Correct 279 ms 130752 KB Output is correct
15 Correct 240 ms 117060 KB Output is correct
16 Correct 358 ms 130760 KB Output is correct
17 Correct 332 ms 136132 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 84604 KB Output is correct
2 Incorrect 79 ms 84564 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 64 ms 81492 KB Output is correct
2 Correct 58 ms 81488 KB Output is correct
3 Correct 76 ms 81488 KB Output is correct
4 Correct 94 ms 81348 KB Output is correct
5 Correct 59 ms 81488 KB Output is correct
6 Correct 58 ms 81300 KB Output is correct
7 Correct 59 ms 81344 KB Output is correct
8 Correct 70 ms 81492 KB Output is correct
9 Correct 72 ms 81452 KB Output is correct
10 Correct 66 ms 81748 KB Output is correct
11 Correct 62 ms 81748 KB Output is correct
12 Correct 67 ms 81772 KB Output is correct
13 Correct 59 ms 81488 KB Output is correct
14 Correct 87 ms 81744 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 81492 KB Output is correct
2 Correct 58 ms 81488 KB Output is correct
3 Correct 76 ms 81488 KB Output is correct
4 Correct 94 ms 81348 KB Output is correct
5 Correct 59 ms 81488 KB Output is correct
6 Correct 58 ms 81300 KB Output is correct
7 Correct 59 ms 81344 KB Output is correct
8 Correct 70 ms 81492 KB Output is correct
9 Correct 72 ms 81452 KB Output is correct
10 Correct 66 ms 81748 KB Output is correct
11 Correct 62 ms 81748 KB Output is correct
12 Correct 67 ms 81772 KB Output is correct
13 Correct 59 ms 81488 KB Output is correct
14 Correct 87 ms 81744 KB Output is correct
15 Correct 58 ms 81748 KB Output is correct
16 Correct 68 ms 82148 KB Output is correct
17 Correct 127 ms 93564 KB Output is correct
18 Correct 128 ms 91220 KB Output is correct
19 Correct 127 ms 92732 KB Output is correct
20 Correct 118 ms 90192 KB Output is correct
21 Correct 115 ms 89860 KB Output is correct
22 Correct 167 ms 98116 KB Output is correct
23 Correct 113 ms 87840 KB Output is correct
24 Correct 142 ms 94888 KB Output is correct
25 Correct 59 ms 81992 KB Output is correct
26 Correct 85 ms 86092 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 81492 KB Output is correct
2 Correct 58 ms 81488 KB Output is correct
3 Correct 76 ms 81488 KB Output is correct
4 Correct 94 ms 81348 KB Output is correct
5 Correct 59 ms 81488 KB Output is correct
6 Correct 58 ms 81300 KB Output is correct
7 Correct 59 ms 81344 KB Output is correct
8 Correct 70 ms 81492 KB Output is correct
9 Correct 72 ms 81452 KB Output is correct
10 Correct 66 ms 81748 KB Output is correct
11 Correct 62 ms 81748 KB Output is correct
12 Correct 67 ms 81772 KB Output is correct
13 Correct 59 ms 81488 KB Output is correct
14 Correct 87 ms 81744 KB Output is correct
15 Correct 58 ms 81748 KB Output is correct
16 Correct 68 ms 82148 KB Output is correct
17 Correct 127 ms 93564 KB Output is correct
18 Correct 128 ms 91220 KB Output is correct
19 Correct 127 ms 92732 KB Output is correct
20 Correct 118 ms 90192 KB Output is correct
21 Correct 115 ms 89860 KB Output is correct
22 Correct 167 ms 98116 KB Output is correct
23 Correct 113 ms 87840 KB Output is correct
24 Correct 142 ms 94888 KB Output is correct
25 Correct 59 ms 81992 KB Output is correct
26 Correct 85 ms 86092 KB Output is correct
27 Incorrect 66 ms 84264 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 103 ms 84604 KB Output is correct
2 Incorrect 79 ms 84564 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 229 ms 124096 KB Output is correct
2 Correct 288 ms 133828 KB Output is correct
3 Correct 87 ms 84556 KB Output is correct
4 Correct 100 ms 84560 KB Output is correct
5 Execution timed out 1093 ms 350436 KB Time limit exceeded
6 Halted 0 ms 0 KB -