oj.uz

Submission #1070817

# Submission time Handle Problem Language Result Execution time Memory
1070817 2024-08-22T19:03:22 Z beaconmc Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 394884 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;
                    if (p[i-1].count(j)) temp = max(temp, suff[i-1][0][j] - p[i-1][j]);
                    if (p[i-1].count(j)) temp = max(temp, suff[i-1][1][j] - p[i-1][j]);
 
                    // 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{
                    if (pref[i-1][0].count(j)) temp = max(temp, pref[i-1][0][j]);
                    if (p[i-2].count(j) && pref[i-1][1].count(j)) temp = max(temp, pref[i-1][1][j] + p[i-2][j]);
 
                    // 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:33: 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++)
......
   67 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:67:9: note: in expansion of macro 'FOR'
   67 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:76:26: 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]
   76 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:74:20: warning: unused variable 'add' [-Wunused-variable]
   74 |                 ll add = 0;
      |                    ^~~
fish.cpp:9:33: 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++)
......
  145 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:145:9: note: in expansion of macro 'FOR'
  145 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 282980 KB Output is correct
2 Correct 534 ms 322620 KB Output is correct
3 Correct 323 ms 214096 KB Output is correct
4 Correct 208 ms 214356 KB Output is correct
5 Execution timed out 1050 ms 338672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107600 KB Output is correct
2 Correct 827 ms 338368 KB Output is correct
3 Execution timed out 1018 ms 372548 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 214096 KB Output is correct
2 Correct 369 ms 214100 KB Output is correct
3 Correct 405 ms 231764 KB Output is correct
4 Correct 408 ms 236388 KB Output is correct
5 Correct 395 ms 263432 KB Output is correct
6 Correct 392 ms 263388 KB Output is correct
7 Correct 433 ms 263616 KB Output is correct
8 Correct 443 ms 263248 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 107604 KB Output is correct
2 Correct 94 ms 107604 KB Output is correct
3 Correct 94 ms 107600 KB Output is correct
4 Correct 75 ms 107564 KB Output is correct
5 Correct 58 ms 107608 KB Output is correct
6 Correct 74 ms 107600 KB Output is correct
7 Correct 89 ms 107604 KB Output is correct
8 Correct 62 ms 107604 KB Output is correct
9 Correct 94 ms 107980 KB Output is correct
10 Correct 66 ms 108880 KB Output is correct
11 Correct 68 ms 108112 KB Output is correct
12 Correct 69 ms 108632 KB Output is correct
13 Correct 61 ms 107600 KB Output is correct
14 Correct 118 ms 108372 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 107604 KB Output is correct
2 Correct 94 ms 107604 KB Output is correct
3 Correct 94 ms 107600 KB Output is correct
4 Correct 75 ms 107564 KB Output is correct
5 Correct 58 ms 107608 KB Output is correct
6 Correct 74 ms 107600 KB Output is correct
7 Correct 89 ms 107604 KB Output is correct
8 Correct 62 ms 107604 KB Output is correct
9 Correct 94 ms 107980 KB Output is correct
10 Correct 66 ms 108880 KB Output is correct
11 Correct 68 ms 108112 KB Output is correct
12 Correct 69 ms 108632 KB Output is correct
13 Correct 61 ms 107600 KB Output is correct
14 Correct 118 ms 108372 KB Output is correct
15 Correct 91 ms 108368 KB Output is correct
16 Correct 99 ms 109140 KB Output is correct
17 Correct 196 ms 140164 KB Output is correct
18 Correct 215 ms 134224 KB Output is correct
19 Correct 206 ms 138144 KB Output is correct
20 Correct 160 ms 131152 KB Output is correct
21 Correct 192 ms 130388 KB Output is correct
22 Correct 251 ms 153540 KB Output is correct
23 Correct 158 ms 123784 KB Output is correct
24 Correct 225 ms 144468 KB Output is correct
25 Correct 68 ms 109180 KB Output is correct
26 Correct 139 ms 119836 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 107604 KB Output is correct
2 Correct 94 ms 107604 KB Output is correct
3 Correct 94 ms 107600 KB Output is correct
4 Correct 75 ms 107564 KB Output is correct
5 Correct 58 ms 107608 KB Output is correct
6 Correct 74 ms 107600 KB Output is correct
7 Correct 89 ms 107604 KB Output is correct
8 Correct 62 ms 107604 KB Output is correct
9 Correct 94 ms 107980 KB Output is correct
10 Correct 66 ms 108880 KB Output is correct
11 Correct 68 ms 108112 KB Output is correct
12 Correct 69 ms 108632 KB Output is correct
13 Correct 61 ms 107600 KB Output is correct
14 Correct 118 ms 108372 KB Output is correct
15 Correct 91 ms 108368 KB Output is correct
16 Correct 99 ms 109140 KB Output is correct
17 Correct 196 ms 140164 KB Output is correct
18 Correct 215 ms 134224 KB Output is correct
19 Correct 206 ms 138144 KB Output is correct
20 Correct 160 ms 131152 KB Output is correct
21 Correct 192 ms 130388 KB Output is correct
22 Correct 251 ms 153540 KB Output is correct
23 Correct 158 ms 123784 KB Output is correct
24 Correct 225 ms 144468 KB Output is correct
25 Correct 68 ms 109180 KB Output is correct
26 Correct 139 ms 119836 KB Output is correct
27 Correct 75 ms 116052 KB Output is correct
28 Correct 719 ms 238824 KB Output is correct
29 Execution timed out 1039 ms 356116 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 214096 KB Output is correct
2 Correct 369 ms 214100 KB Output is correct
3 Correct 405 ms 231764 KB Output is correct
4 Correct 408 ms 236388 KB Output is correct
5 Correct 395 ms 263432 KB Output is correct
6 Correct 392 ms 263388 KB Output is correct
7 Correct 433 ms 263616 KB Output is correct
8 Correct 443 ms 263248 KB Output is correct
9 Correct 848 ms 394884 KB Output is correct
10 Correct 322 ms 203752 KB Output is correct
11 Correct 656 ms 300368 KB Output is correct
12 Correct 61 ms 107604 KB Output is correct
13 Correct 96 ms 107604 KB Output is correct
14 Correct 59 ms 107580 KB Output is correct
15 Correct 81 ms 107636 KB Output is correct
16 Correct 99 ms 107600 KB Output is correct
17 Correct 66 ms 107568 KB Output is correct
18 Correct 208 ms 213968 KB Output is correct
19 Correct 204 ms 213872 KB Output is correct
20 Correct 204 ms 214100 KB Output is correct
21 Correct 328 ms 214096 KB Output is correct
22 Execution timed out 1029 ms 391760 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 282980 KB Output is correct
2 Correct 534 ms 322620 KB Output is correct
3 Correct 323 ms 214096 KB Output is correct
4 Correct 208 ms 214356 KB Output is correct
5 Execution timed out 1050 ms 338672 KB Time limit exceeded
6 Halted 0 ms 0 KB -