oj.uz

Submission #1070816

# Submission time Handle Problem Language Result Execution time Memory
1070816 2024-08-22T19:02:29 Z beaconmc Catfish Farm (IOI22_fish) C++17
20 / 100
 1000 ms 341172 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){
        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++)
......
   66 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:66:9: note: in expansion of macro 'FOR'
   66 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:75: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]
   75 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:73:20: warning: unused variable 'add' [-Wunused-variable]
   73 |                 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++)
......
  144 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:144:9: note: in expansion of macro 'FOR'
  144 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 252588 KB Output is correct
2 Correct 535 ms 291584 KB Output is correct
3 Correct 209 ms 182612 KB Output is correct
4 Correct 228 ms 182612 KB Output is correct
5 Execution timed out 1046 ms 321308 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 84052 KB Output is correct
2 Correct 972 ms 307872 KB Output is correct
3 Correct 938 ms 341172 KB Output is correct
4 Correct 432 ms 252520 KB Output is correct
5 Correct 602 ms 291388 KB Output is correct
6 Correct 55 ms 84172 KB Output is correct
7 Correct 34 ms 83988 KB Output is correct
8 Correct 39 ms 84048 KB Output is correct
9 Correct 37 ms 84048 KB Output is correct
10 Correct 310 ms 182612 KB Output is correct
11 Correct 237 ms 182612 KB Output is correct
12 Correct 554 ms 284172 KB Output is correct
13 Correct 686 ms 334392 KB Output is correct
14 Correct 567 ms 268448 KB Output is correct
15 Correct 453 ms 259124 KB Output is correct
16 Correct 616 ms 268444 KB Output is correct
17 Correct 699 ms 303040 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 182612 KB Output is correct
2 Correct 194 ms 182700 KB Output is correct
3 Incorrect 364 ms 200272 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21252878690860'
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 84052 KB Output is correct
2 Correct 36 ms 84060 KB Output is correct
3 Correct 53 ms 84096 KB Output is correct
4 Correct 36 ms 84052 KB Output is correct
5 Correct 34 ms 84048 KB Output is correct
6 Correct 35 ms 84048 KB Output is correct
7 Correct 34 ms 84060 KB Output is correct
8 Correct 36 ms 84048 KB Output is correct
9 Correct 58 ms 84564 KB Output is correct
10 Correct 52 ms 85328 KB Output is correct
11 Correct 50 ms 84572 KB Output is correct
12 Correct 52 ms 85320 KB Output is correct
13 Correct 49 ms 84352 KB Output is correct
14 Correct 37 ms 84824 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 84052 KB Output is correct
2 Correct 36 ms 84060 KB Output is correct
3 Correct 53 ms 84096 KB Output is correct
4 Correct 36 ms 84052 KB Output is correct
5 Correct 34 ms 84048 KB Output is correct
6 Correct 35 ms 84048 KB Output is correct
7 Correct 34 ms 84060 KB Output is correct
8 Correct 36 ms 84048 KB Output is correct
9 Correct 58 ms 84564 KB Output is correct
10 Correct 52 ms 85328 KB Output is correct
11 Correct 50 ms 84572 KB Output is correct
12 Correct 52 ms 85320 KB Output is correct
13 Correct 49 ms 84352 KB Output is correct
14 Correct 37 ms 84824 KB Output is correct
15 Correct 45 ms 84820 KB Output is correct
16 Incorrect 53 ms 85812 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '737888996850'
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 84052 KB Output is correct
2 Correct 36 ms 84060 KB Output is correct
3 Correct 53 ms 84096 KB Output is correct
4 Correct 36 ms 84052 KB Output is correct
5 Correct 34 ms 84048 KB Output is correct
6 Correct 35 ms 84048 KB Output is correct
7 Correct 34 ms 84060 KB Output is correct
8 Correct 36 ms 84048 KB Output is correct
9 Correct 58 ms 84564 KB Output is correct
10 Correct 52 ms 85328 KB Output is correct
11 Correct 50 ms 84572 KB Output is correct
12 Correct 52 ms 85320 KB Output is correct
13 Correct 49 ms 84352 KB Output is correct
14 Correct 37 ms 84824 KB Output is correct
15 Correct 45 ms 84820 KB Output is correct
16 Incorrect 53 ms 85812 KB 1st lines differ - on the 1st token, expected: '741526820812', found: '737888996850'
17 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 182612 KB Output is correct
2 Correct 194 ms 182700 KB Output is correct
3 Incorrect 364 ms 200272 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '21252878690860'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 252588 KB Output is correct
2 Correct 535 ms 291584 KB Output is correct
3 Correct 209 ms 182612 KB Output is correct
4 Correct 228 ms 182612 KB Output is correct
5 Execution timed out 1046 ms 321308 KB Time limit exceeded
6 Halted 0 ms 0 KB -