oj.uz

Submission #1070815

# Submission time Handle Problem Language Result Execution time Memory
1070815 2024-08-22T18:58:48 Z beaconmc Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 437072 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++)
......
   65 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:65:9: note: in expansion of macro 'FOR'
   65 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:74: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]
   74 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:72:20: warning: unused variable 'add' [-Wunused-variable]
   72 |                 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++)
......
  143 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:143:9: note: in expansion of macro 'FOR'
  143 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 282980 KB Output is correct
2 Correct 534 ms 324408 KB Output is correct
3 Correct 211 ms 214100 KB Output is correct
4 Correct 202 ms 213936 KB Output is correct
5 Execution timed out 1053 ms 404564 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 107600 KB Output is correct
2 Correct 862 ms 338364 KB Output is correct
3 Correct 945 ms 376004 KB Output is correct
4 Correct 408 ms 284564 KB Output is correct
5 Correct 556 ms 324576 KB Output is correct
6 Correct 58 ms 107604 KB Output is correct
7 Correct 59 ms 107604 KB Output is correct
8 Correct 87 ms 107604 KB Output is correct
9 Correct 59 ms 107600 KB Output is correct
10 Correct 212 ms 214096 KB Output is correct
11 Correct 194 ms 214100 KB Output is correct
12 Correct 539 ms 316064 KB Output is correct
13 Correct 650 ms 367420 KB Output is correct
14 Correct 684 ms 300168 KB Output is correct
15 Correct 463 ms 292152 KB Output is correct
16 Correct 592 ms 300520 KB Output is correct
17 Correct 644 ms 335804 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 214012 KB Output is correct
2 Correct 185 ms 214036 KB Output is correct
3 Correct 301 ms 231764 KB Output is correct
4 Correct 252 ms 236304 KB Output is correct
5 Correct 378 ms 263268 KB Output is correct
6 Correct 594 ms 263360 KB Output is correct
7 Correct 440 ms 263200 KB Output is correct
8 Correct 361 ms 263252 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 107604 KB Output is correct
2 Correct 86 ms 107600 KB Output is correct
3 Correct 90 ms 107604 KB Output is correct
4 Correct 62 ms 107596 KB Output is correct
5 Correct 90 ms 107604 KB Output is correct
6 Correct 93 ms 107604 KB Output is correct
7 Correct 78 ms 107600 KB Output is correct
8 Correct 60 ms 107664 KB Output is correct
9 Correct 88 ms 107856 KB Output is correct
10 Correct 75 ms 108928 KB Output is correct
11 Correct 61 ms 108116 KB Output is correct
12 Correct 62 ms 108716 KB Output is correct
13 Correct 59 ms 107840 KB Output is correct
14 Correct 100 ms 108372 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 107604 KB Output is correct
2 Correct 86 ms 107600 KB Output is correct
3 Correct 90 ms 107604 KB Output is correct
4 Correct 62 ms 107596 KB Output is correct
5 Correct 90 ms 107604 KB Output is correct
6 Correct 93 ms 107604 KB Output is correct
7 Correct 78 ms 107600 KB Output is correct
8 Correct 60 ms 107664 KB Output is correct
9 Correct 88 ms 107856 KB Output is correct
10 Correct 75 ms 108928 KB Output is correct
11 Correct 61 ms 108116 KB Output is correct
12 Correct 62 ms 108716 KB Output is correct
13 Correct 59 ms 107840 KB Output is correct
14 Correct 100 ms 108372 KB Output is correct
15 Correct 61 ms 108444 KB Output is correct
16 Correct 66 ms 109140 KB Output is correct
17 Correct 175 ms 140072 KB Output is correct
18 Correct 155 ms 134228 KB Output is correct
19 Correct 168 ms 138324 KB Output is correct
20 Correct 180 ms 131156 KB Output is correct
21 Correct 147 ms 130356 KB Output is correct
22 Correct 252 ms 153444 KB Output is correct
23 Correct 119 ms 123984 KB Output is correct
24 Correct 207 ms 144480 KB Output is correct
25 Correct 65 ms 109144 KB Output is correct
26 Correct 128 ms 119892 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 107604 KB Output is correct
2 Correct 86 ms 107600 KB Output is correct
3 Correct 90 ms 107604 KB Output is correct
4 Correct 62 ms 107596 KB Output is correct
5 Correct 90 ms 107604 KB Output is correct
6 Correct 93 ms 107604 KB Output is correct
7 Correct 78 ms 107600 KB Output is correct
8 Correct 60 ms 107664 KB Output is correct
9 Correct 88 ms 107856 KB Output is correct
10 Correct 75 ms 108928 KB Output is correct
11 Correct 61 ms 108116 KB Output is correct
12 Correct 62 ms 108716 KB Output is correct
13 Correct 59 ms 107840 KB Output is correct
14 Correct 100 ms 108372 KB Output is correct
15 Correct 61 ms 108444 KB Output is correct
16 Correct 66 ms 109140 KB Output is correct
17 Correct 175 ms 140072 KB Output is correct
18 Correct 155 ms 134228 KB Output is correct
19 Correct 168 ms 138324 KB Output is correct
20 Correct 180 ms 131156 KB Output is correct
21 Correct 147 ms 130356 KB Output is correct
22 Correct 252 ms 153444 KB Output is correct
23 Correct 119 ms 123984 KB Output is correct
24 Correct 207 ms 144480 KB Output is correct
25 Correct 65 ms 109144 KB Output is correct
26 Correct 128 ms 119892 KB Output is correct
27 Correct 75 ms 116196 KB Output is correct
28 Correct 666 ms 238748 KB Output is correct
29 Execution timed out 1054 ms 412240 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 214012 KB Output is correct
2 Correct 185 ms 214036 KB Output is correct
3 Correct 301 ms 231764 KB Output is correct
4 Correct 252 ms 236304 KB Output is correct
5 Correct 378 ms 263268 KB Output is correct
6 Correct 594 ms 263360 KB Output is correct
7 Correct 440 ms 263200 KB Output is correct
8 Correct 361 ms 263252 KB Output is correct
9 Correct 770 ms 394760 KB Output is correct
10 Correct 370 ms 205588 KB Output is correct
11 Correct 571 ms 303700 KB Output is correct
12 Correct 58 ms 107664 KB Output is correct
13 Correct 88 ms 107600 KB Output is correct
14 Correct 61 ms 107604 KB Output is correct
15 Correct 63 ms 107524 KB Output is correct
16 Correct 66 ms 107600 KB Output is correct
17 Correct 81 ms 107608 KB Output is correct
18 Correct 189 ms 214100 KB Output is correct
19 Correct 190 ms 214100 KB Output is correct
20 Correct 183 ms 214044 KB Output is correct
21 Correct 298 ms 214060 KB Output is correct
22 Correct 898 ms 393988 KB Output is correct
23 Correct 854 ms 404252 KB Output is correct
24 Execution timed out 1046 ms 437072 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 282980 KB Output is correct
2 Correct 534 ms 324408 KB Output is correct
3 Correct 211 ms 214100 KB Output is correct
4 Correct 202 ms 213936 KB Output is correct
5 Execution timed out 1053 ms 404564 KB Time limit exceeded
6 Halted 0 ms 0 KB -