oj.uz

Submission #1070843

# Submission time Handle Problem Language Result Execution time Memory
1070843 2024-08-22T19:30:32 Z beaconmc Catfish Farm (IOI22_fish) C++17
50 / 100
 1000 ms 413520 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;
                    temp = max(temp, suff[i-1][0][j] - p[i-1][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{
                    temp = max(temp, pref[i-1][0][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 605 ms 282980 KB Output is correct
2 Correct 566 ms 322620 KB Output is correct
3 Correct 200 ms 213892 KB Output is correct
4 Correct 307 ms 214100 KB Output is correct
5 Execution timed out 1078 ms 336816 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 107604 KB Output is correct
2 Correct 892 ms 338412 KB Output is correct
3 Correct 895 ms 372420 KB Output is correct
4 Correct 452 ms 282988 KB Output is correct
5 Correct 532 ms 322620 KB Output is correct
6 Correct 62 ms 107604 KB Output is correct
7 Correct 79 ms 107604 KB Output is correct
8 Correct 100 ms 107568 KB Output is correct
9 Correct 67 ms 107604 KB Output is correct
10 Correct 201 ms 214100 KB Output is correct
11 Correct 323 ms 213968 KB Output is correct
12 Correct 560 ms 314604 KB Output is correct
13 Correct 748 ms 365628 KB Output is correct
14 Correct 663 ms 298800 KB Output is correct
15 Correct 616 ms 290896 KB Output is correct
16 Correct 553 ms 298968 KB Output is correct
17 Correct 787 ms 334232 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 213932 KB Output is correct
2 Correct 283 ms 213912 KB Output is correct
3 Correct 269 ms 231764 KB Output is correct
4 Correct 448 ms 236880 KB Output is correct
5 Correct 397 ms 263332 KB Output is correct
6 Correct 529 ms 263404 KB Output is correct
7 Correct 370 ms 263416 KB Output is correct
8 Correct 377 ms 263256 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 107604 KB Output is correct
2 Correct 90 ms 107604 KB Output is correct
3 Correct 60 ms 107600 KB Output is correct
4 Correct 105 ms 107520 KB Output is correct
5 Correct 70 ms 107860 KB Output is correct
6 Correct 59 ms 107604 KB Output is correct
7 Correct 62 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 97 ms 107860 KB Output is correct
10 Correct 88 ms 108884 KB Output is correct
11 Correct 74 ms 108268 KB Output is correct
12 Correct 68 ms 108628 KB Output is correct
13 Correct 66 ms 107600 KB Output is correct
14 Correct 109 ms 108372 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 107604 KB Output is correct
2 Correct 90 ms 107604 KB Output is correct
3 Correct 60 ms 107600 KB Output is correct
4 Correct 105 ms 107520 KB Output is correct
5 Correct 70 ms 107860 KB Output is correct
6 Correct 59 ms 107604 KB Output is correct
7 Correct 62 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 97 ms 107860 KB Output is correct
10 Correct 88 ms 108884 KB Output is correct
11 Correct 74 ms 108268 KB Output is correct
12 Correct 68 ms 108628 KB Output is correct
13 Correct 66 ms 107600 KB Output is correct
14 Correct 109 ms 108372 KB Output is correct
15 Correct 74 ms 108372 KB Output is correct
16 Correct 68 ms 109176 KB Output is correct
17 Correct 207 ms 141008 KB Output is correct
18 Correct 207 ms 134448 KB Output is correct
19 Correct 182 ms 139604 KB Output is correct
20 Correct 155 ms 131276 KB Output is correct
21 Correct 155 ms 130388 KB Output is correct
22 Correct 270 ms 153684 KB Output is correct
23 Correct 160 ms 125660 KB Output is correct
24 Correct 209 ms 145748 KB Output is correct
25 Correct 113 ms 109396 KB Output is correct
26 Correct 107 ms 120500 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 107604 KB Output is correct
2 Correct 90 ms 107604 KB Output is correct
3 Correct 60 ms 107600 KB Output is correct
4 Correct 105 ms 107520 KB Output is correct
5 Correct 70 ms 107860 KB Output is correct
6 Correct 59 ms 107604 KB Output is correct
7 Correct 62 ms 107600 KB Output is correct
8 Correct 65 ms 107600 KB Output is correct
9 Correct 97 ms 107860 KB Output is correct
10 Correct 88 ms 108884 KB Output is correct
11 Correct 74 ms 108268 KB Output is correct
12 Correct 68 ms 108628 KB Output is correct
13 Correct 66 ms 107600 KB Output is correct
14 Correct 109 ms 108372 KB Output is correct
15 Correct 74 ms 108372 KB Output is correct
16 Correct 68 ms 109176 KB Output is correct
17 Correct 207 ms 141008 KB Output is correct
18 Correct 207 ms 134448 KB Output is correct
19 Correct 182 ms 139604 KB Output is correct
20 Correct 155 ms 131276 KB Output is correct
21 Correct 155 ms 130388 KB Output is correct
22 Correct 270 ms 153684 KB Output is correct
23 Correct 160 ms 125660 KB Output is correct
24 Correct 209 ms 145748 KB Output is correct
25 Correct 113 ms 109396 KB Output is correct
26 Correct 107 ms 120500 KB Output is correct
27 Correct 82 ms 116736 KB Output is correct
28 Correct 711 ms 239444 KB Output is correct
29 Execution timed out 1098 ms 394128 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 213932 KB Output is correct
2 Correct 283 ms 213912 KB Output is correct
3 Correct 269 ms 231764 KB Output is correct
4 Correct 448 ms 236880 KB Output is correct
5 Correct 397 ms 263332 KB Output is correct
6 Correct 529 ms 263404 KB Output is correct
7 Correct 370 ms 263416 KB Output is correct
8 Correct 377 ms 263256 KB Output is correct
9 Correct 997 ms 413520 KB Output is correct
10 Correct 348 ms 203856 KB Output is correct
11 Correct 579 ms 300116 KB Output is correct
12 Correct 66 ms 107604 KB Output is correct
13 Correct 63 ms 107600 KB Output is correct
14 Correct 66 ms 107416 KB Output is correct
15 Correct 85 ms 107600 KB Output is correct
16 Correct 63 ms 107660 KB Output is correct
17 Correct 65 ms 107600 KB Output is correct
18 Correct 331 ms 214096 KB Output is correct
19 Correct 224 ms 214356 KB Output is correct
20 Correct 197 ms 214100 KB Output is correct
21 Correct 199 ms 213876 KB Output is correct
22 Correct 904 ms 411044 KB Output is correct
23 Execution timed out 1018 ms 408768 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 282980 KB Output is correct
2 Correct 566 ms 322620 KB Output is correct
3 Correct 200 ms 213892 KB Output is correct
4 Correct 307 ms 214100 KB Output is correct
5 Execution timed out 1078 ms 336816 KB Time limit exceeded
6 Halted 0 ms 0 KB -