oj.uz

Submission #1042312

# Submission time Handle Problem Language Result Execution time Memory
1042312 2024-08-02T20:22:43 Z VMaksimoski008 Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 106580 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")
 
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for(int i=0; i<M; i++) X[i]++, Y[i]++;
    map<int, int> mp[N+5];
    for(int i=0; i<M; i++) mp[X[i]][Y[i]] = W[i];
    ll ans = 0;

    vector<pair<int, int> > vec[N+5];
    vector<int> pos[N+5], SZ(N+5);
    for(int i=1; i<=N; i++) vec[i].push_back({ 0, 0 });
    for(int i=0; i<M; i++) vec[X[i]].push_back({ Y[i], W[i] });
    for(int i=1; i<=N; i++) {
        set<int> st;
        for(auto &x : vec[i-1]) st.insert(x.first);
        for(auto &x : vec[i]) st.insert(x.first);
        for(auto &x : vec[i+1]) st.insert(x.first);
        for(auto &x : st) pos[i].push_back(x);
        sort(vec[i].begin(), vec[i].end());
        // cout << i << ": ";
        // for(int &x : pos[i]) cout << x << " ";
        // cout << '\n';
    }

    vector<vector<ll> > pref(N+5);
    vector<vector<vector<ll> > > dp(N+5);
    for(int i=1; i<=N; i++) {
        SZ[i] = pos[i].size() - 1;
        pref[i].resize(SZ[i] + 5);
        dp[i].resize(SZ[i] + 5, vector<ll>(2));
        for(int j=1; j<=SZ[i]; j++) pref[i][j] = pref[i][j-1] + mp[i][pos[i][j]];
        // cout << i << ": ";
        // for(ll &x : pref[i]) cout << x << " ";
        // cout << '\n';
    }

    for(int i=2; i<=N; i++) {
        for(int j=0; j<=SZ[i]; j++) {
            // cout << i << " " << pos[i][j] << '\n';
            for(int k=0; k<=SZ[i-1]; k++) {
                if(pos[i][j] >= pos[i-1][k]) {
                    int p = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
                    dp[i][j][1] = max(dp[i][j][1], dp[i-1][k][1] + pref[i-1][p] - pref[i-1][k]);
                }

                if(pos[i][j] <= pos[i-1][k]) {
                    int p = upper_bound(pos[i].begin(), pos[i].end(), pos[i-1][k]) - pos[i].begin() - 1;
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i-1][k][0], dp[i-1][k][1]) + pref[i][p] - pref[i][j]);
                }
            }

            if(i < 3) continue;
            for(int k=0; k<=SZ[i-2]; k++) {
                int p1 = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i][j]) - pos[i-1].begin() - 1;
                int p2 = upper_bound(pos[i-1].begin(), pos[i-1].end(), pos[i-2][k]) - pos[i-1].begin() - 1;
                dp[i][j][0] = max(dp[i][j][0], max(dp[i-2][k][0], dp[i-2][k][1]) + max((p1 > -1 ? pref[i-1][p1] : 0), (p2 > -1 ? pref[i-1][p2] : 0)));
                dp[i][j][1] = max(dp[i][j][1], max(dp[i-2][k][0], dp[i-2][k][1]) + max((p1 > -1 ? pref[i-1][p1] : 0), (p2 > -1 ? pref[i-1][p2] : 0)));
            }
        }
    }

    for(int i=1; i<=N; i++) {
        for(int j=0; j<=SZ[i]; j++) {
            if(pref[i+1].empty() || j == 0) ans = max({ ans, dp[i][j][0], dp[i][j][1] });
            else {
                int p = upper_bound(pos[i+1].begin(), pos[i+1].end(), pos[i][j]) - pos[i+1].begin() - 1;
                ans = max(ans, max(dp[i][j][0], dp[i][j][1]) + pref[i+1][p]);
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1074 ms 83172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 53840 KB Output is correct
2 Correct 57 ms 53968 KB Output is correct
3 Correct 82 ms 57212 KB Output is correct
4 Correct 83 ms 60244 KB Output is correct
5 Correct 128 ms 68812 KB Output is correct
6 Correct 113 ms 68692 KB Output is correct
7 Correct 114 ms 68692 KB Output is correct
8 Correct 113 ms 68688 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 9 ms 860 KB Output is correct
17 Correct 652 ms 9136 KB Output is correct
18 Correct 601 ms 8260 KB Output is correct
19 Correct 367 ms 8284 KB Output is correct
20 Correct 294 ms 7364 KB Output is correct
21 Correct 277 ms 7476 KB Output is correct
22 Execution timed out 1041 ms 14160 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 9 ms 860 KB Output is correct
17 Correct 652 ms 9136 KB Output is correct
18 Correct 601 ms 8260 KB Output is correct
19 Correct 367 ms 8284 KB Output is correct
20 Correct 294 ms 7364 KB Output is correct
21 Correct 277 ms 7476 KB Output is correct
22 Execution timed out 1041 ms 14160 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 53840 KB Output is correct
2 Correct 57 ms 53968 KB Output is correct
3 Correct 82 ms 57212 KB Output is correct
4 Correct 83 ms 60244 KB Output is correct
5 Correct 128 ms 68812 KB Output is correct
6 Correct 113 ms 68692 KB Output is correct
7 Correct 114 ms 68692 KB Output is correct
8 Correct 113 ms 68688 KB Output is correct
9 Correct 167 ms 90708 KB Output is correct
10 Correct 82 ms 41452 KB Output is correct
11 Correct 184 ms 82512 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 59 ms 53884 KB Output is correct
19 Correct 59 ms 53844 KB Output is correct
20 Correct 55 ms 53860 KB Output is correct
21 Correct 60 ms 53848 KB Output is correct
22 Correct 226 ms 90960 KB Output is correct
23 Correct 265 ms 104272 KB Output is correct
24 Correct 296 ms 106580 KB Output is correct

Subtask #8
0 / 16.0

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