oj.uz

Submission #1070807

# Submission time Handle Problem Language Result Execution time Memory
1070807 2024-08-22T18:52:11 Z beaconmc Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 1061636 KB 
#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> 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,maxn) weights[i].reserve(128);
FOR(i,0,M){
    Y[i]++;

    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);
//131072

FOR(i,0,maxn){
    p[i].reserve(128);
    FOR(k,0,2){
        pref[i][k].reserve(128);
        pref2[i][k].reserve(128);
        suff[i][k].reserve(128);
    }
}
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;
                ll up = *upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]);
                ll down = *(--upper_bound(realheights[i-1].begin(), realheights[i-1].end(), realheights[i][X]));
                temp = max(temp, suff[i-1][0][up] - p[i-1][down]);
                temp = max(temp, suff[i-1][1][up] - 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(), realheights[i][X]));
                ll down2 = *(--upper_bound(realheights[i-2].begin(), realheights[i-2].end(), realheights[i][X]));

                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][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:7: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]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   73 |     FOR(X,0,dp[i].size()){
      |         ~~~~~~~~~~~~~~~~         
fish.cpp:73:5: note: in expansion of macro 'FOR'
   73 |     FOR(X,0,dp[i].size()){
      |     ^~~
fish.cpp:82:22: 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]
   82 |                 if (X==dp[i].size()-1) continue;
      |                     ~^~~~~~~~~~~~~~~~
fish.cpp:80:16: warning: unused variable 'add' [-Wunused-variable]
   80 |             ll add = 0;
      |                ^~~
fish.cpp:74:12: warning: unused variable 'j' [-Wunused-variable]
   74 |         ll j = realheights[i][X];
      |            ^
fish.cpp:7: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]
    7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  156 |     FOR(j,0,dp[i].size()){
      |         ~~~~~~~~~~~~~~~~         
fish.cpp:156:5: note: in expansion of macro 'FOR'
  156 |     FOR(j,0,dp[i].size()){
      |     ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 1059896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 944516 KB Output is correct
2 Execution timed out 1108 ms 1034000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 985168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 944340 KB Output is correct
2 Correct 794 ms 944472 KB Output is correct
3 Correct 954 ms 944468 KB Output is correct
4 Correct 805 ms 944468 KB Output is correct
5 Correct 846 ms 944432 KB Output is correct
6 Correct 827 ms 944468 KB Output is correct
7 Correct 801 ms 944476 KB Output is correct
8 Correct 812 ms 944464 KB Output is correct
9 Correct 807 ms 944720 KB Output is correct
10 Correct 809 ms 945488 KB Output is correct
11 Correct 853 ms 944980 KB Output is correct
12 Correct 794 ms 945412 KB Output is correct
13 Correct 821 ms 944724 KB Output is correct
14 Correct 840 ms 945008 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 944340 KB Output is correct
2 Correct 794 ms 944472 KB Output is correct
3 Correct 954 ms 944468 KB Output is correct
4 Correct 805 ms 944468 KB Output is correct
5 Correct 846 ms 944432 KB Output is correct
6 Correct 827 ms 944468 KB Output is correct
7 Correct 801 ms 944476 KB Output is correct
8 Correct 812 ms 944464 KB Output is correct
9 Correct 807 ms 944720 KB Output is correct
10 Correct 809 ms 945488 KB Output is correct
11 Correct 853 ms 944980 KB Output is correct
12 Correct 794 ms 945412 KB Output is correct
13 Correct 821 ms 944724 KB Output is correct
14 Correct 840 ms 945008 KB Output is correct
15 Correct 814 ms 945048 KB Output is correct
16 Correct 773 ms 945492 KB Output is correct
17 Correct 910 ms 974328 KB Output is correct
18 Correct 867 ms 968528 KB Output is correct
19 Correct 910 ms 971860 KB Output is correct
20 Correct 887 ms 964432 KB Output is correct
21 Correct 851 ms 963668 KB Output is correct
22 Correct 923 ms 985936 KB Output is correct
23 Correct 814 ms 957524 KB Output is correct
24 Correct 876 ms 974152 KB Output is correct
25 Correct 804 ms 945780 KB Output is correct
26 Correct 856 ms 954088 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 944340 KB Output is correct
2 Correct 794 ms 944472 KB Output is correct
3 Correct 954 ms 944468 KB Output is correct
4 Correct 805 ms 944468 KB Output is correct
5 Correct 846 ms 944432 KB Output is correct
6 Correct 827 ms 944468 KB Output is correct
7 Correct 801 ms 944476 KB Output is correct
8 Correct 812 ms 944464 KB Output is correct
9 Correct 807 ms 944720 KB Output is correct
10 Correct 809 ms 945488 KB Output is correct
11 Correct 853 ms 944980 KB Output is correct
12 Correct 794 ms 945412 KB Output is correct
13 Correct 821 ms 944724 KB Output is correct
14 Correct 840 ms 945008 KB Output is correct
15 Correct 814 ms 945048 KB Output is correct
16 Correct 773 ms 945492 KB Output is correct
17 Correct 910 ms 974328 KB Output is correct
18 Correct 867 ms 968528 KB Output is correct
19 Correct 910 ms 971860 KB Output is correct
20 Correct 887 ms 964432 KB Output is correct
21 Correct 851 ms 963668 KB Output is correct
22 Correct 923 ms 985936 KB Output is correct
23 Correct 814 ms 957524 KB Output is correct
24 Correct 876 ms 974152 KB Output is correct
25 Correct 804 ms 945780 KB Output is correct
26 Correct 856 ms 954088 KB Output is correct
27 Correct 849 ms 950612 KB Output is correct
28 Execution timed out 1118 ms 1061636 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 985168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 1059896 KB Time limit exceeded
2 Halted 0 ms 0 KB -