oj.uz

Submission #1080485

# Submission time Handle Problem Language Result Execution time Memory
1080485 2024-08-29T10:22:02 Z Wansur Catfish Farm (IOI22_fish) C++17
58 / 100
 1000 ms 305280 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 12;

vector<int> s[maxn];
map<int, ll> dp[maxn], dpt[maxn], d[maxn];
map<int, ll> pref[maxn], mx[maxn], suff[maxn];
map<int, ll>  a[maxn], mval[maxn];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    ll ans = 0;
    for(int i=0;i<m;i++){
        x[i]++, y[i]++;
        a[x[i]][y[i]] += w[i];
        for(int d=-1;d<=1;d++){
            s[x[i] + d].push_back(y[i]);
        }
    }
    s[0] = {0};
    for(int i=1;i<=n;i++){
        s[i].push_back(0);
        sort(s[i].begin(), s[i].end());
        s[i].resize(unique(s[i].begin(), s[i].end()) - s[i].begin());
        ll sum = 0;
        for(int x:s[i]){
            sum += a[i][x];
            pref[i][x] = sum;
        }
    }
    for(int i=1;i<=n;i++){

        ll val = -1e18;

        for(int x:s[i]){
            auto it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin() - 1;
            int y = s[i-1][it];
            dp[i][x] = max(mx[i-1][y] + pref[i-1][y], mval[i-1][y]);
            d[i][x] = max(dp[i][x], suff[i-1][y] - pref[i][x]);
            val = max(val, d[i][x]);
            mval[i][x] = val;
            ans = max(ans, d[i][x]);
        }

        for(auto x:s[i-1]){
            auto it = upper_bound(s[i].begin(), s[i].end(), x) - s[i].begin() - 1;
            int y = s[i][it];
            dpt[i][x] = d[i-1][x] + pref[i][y];
        }

        val = -1e18;

        for(int x:s[i]){
            auto it = upper_bound(s[i-1].begin(), s[i-1].end(), x) - s[i-1].begin() - 1;
            int y = s[i-1][it];

            val = max(val, max(dp[i][x], dpt[i][y]) - pref[i][x]);
            mx[i][x] = val;
        }

        val = -1e18;

        if(i < n){
            for(int j=(int)s[i].size() - 1;j>=0;j--){
                int x = s[i][j];
                auto it = upper_bound(s[i+1].begin(), s[i+1].end(), x) - s[i+1].begin() - 1;
                int y = s[i+1][it];

                val = max(val, d[i][x] + pref[i+1][y]);
                suff[i][x] = val;
            }
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 173208 KB Output is correct
2 Correct 723 ms 198820 KB Output is correct
3 Correct 78 ms 93528 KB Output is correct
4 Correct 75 ms 93524 KB Output is correct
5 Execution timed out 1040 ms 272476 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40284 KB Output is correct
2 Execution timed out 1029 ms 226532 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 93520 KB Output is correct
2 Correct 76 ms 93556 KB Output is correct
3 Correct 155 ms 120056 KB Output is correct
4 Correct 152 ms 117140 KB Output is correct
5 Correct 244 ms 147536 KB Output is correct
6 Correct 258 ms 146776 KB Output is correct
7 Correct 221 ms 147536 KB Output is correct
8 Correct 231 ms 147364 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40280 KB Output is correct
2 Correct 20 ms 40256 KB Output is correct
3 Correct 19 ms 40280 KB Output is correct
4 Correct 19 ms 40280 KB Output is correct
5 Correct 19 ms 40240 KB Output is correct
6 Correct 19 ms 40164 KB Output is correct
7 Correct 19 ms 40280 KB Output is correct
8 Correct 19 ms 40280 KB Output is correct
9 Correct 20 ms 40536 KB Output is correct
10 Correct 20 ms 41816 KB Output is correct
11 Correct 24 ms 40872 KB Output is correct
12 Correct 21 ms 41564 KB Output is correct
13 Correct 17 ms 40540 KB Output is correct
14 Correct 19 ms 41052 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40280 KB Output is correct
2 Correct 20 ms 40256 KB Output is correct
3 Correct 19 ms 40280 KB Output is correct
4 Correct 19 ms 40280 KB Output is correct
5 Correct 19 ms 40240 KB Output is correct
6 Correct 19 ms 40164 KB Output is correct
7 Correct 19 ms 40280 KB Output is correct
8 Correct 19 ms 40280 KB Output is correct
9 Correct 20 ms 40536 KB Output is correct
10 Correct 20 ms 41816 KB Output is correct
11 Correct 24 ms 40872 KB Output is correct
12 Correct 21 ms 41564 KB Output is correct
13 Correct 17 ms 40540 KB Output is correct
14 Correct 19 ms 41052 KB Output is correct
15 Correct 20 ms 40796 KB Output is correct
16 Correct 23 ms 41820 KB Output is correct
17 Correct 149 ms 73556 KB Output is correct
18 Correct 127 ms 68436 KB Output is correct
19 Correct 120 ms 69812 KB Output is correct
20 Correct 103 ms 65876 KB Output is correct
21 Correct 94 ms 65364 KB Output is correct
22 Correct 221 ms 90192 KB Output is correct
23 Correct 60 ms 53076 KB Output is correct
24 Correct 137 ms 73812 KB Output is correct
25 Correct 21 ms 41820 KB Output is correct
26 Correct 50 ms 51112 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40280 KB Output is correct
2 Correct 20 ms 40256 KB Output is correct
3 Correct 19 ms 40280 KB Output is correct
4 Correct 19 ms 40280 KB Output is correct
5 Correct 19 ms 40240 KB Output is correct
6 Correct 19 ms 40164 KB Output is correct
7 Correct 19 ms 40280 KB Output is correct
8 Correct 19 ms 40280 KB Output is correct
9 Correct 20 ms 40536 KB Output is correct
10 Correct 20 ms 41816 KB Output is correct
11 Correct 24 ms 40872 KB Output is correct
12 Correct 21 ms 41564 KB Output is correct
13 Correct 17 ms 40540 KB Output is correct
14 Correct 19 ms 41052 KB Output is correct
15 Correct 20 ms 40796 KB Output is correct
16 Correct 23 ms 41820 KB Output is correct
17 Correct 149 ms 73556 KB Output is correct
18 Correct 127 ms 68436 KB Output is correct
19 Correct 120 ms 69812 KB Output is correct
20 Correct 103 ms 65876 KB Output is correct
21 Correct 94 ms 65364 KB Output is correct
22 Correct 221 ms 90192 KB Output is correct
23 Correct 60 ms 53076 KB Output is correct
24 Correct 137 ms 73812 KB Output is correct
25 Correct 21 ms 41820 KB Output is correct
26 Correct 50 ms 51112 KB Output is correct
27 Correct 25 ms 46520 KB Output is correct
28 Correct 663 ms 187840 KB Output is correct
29 Execution timed out 1113 ms 302672 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 93520 KB Output is correct
2 Correct 76 ms 93556 KB Output is correct
3 Correct 155 ms 120056 KB Output is correct
4 Correct 152 ms 117140 KB Output is correct
5 Correct 244 ms 147536 KB Output is correct
6 Correct 258 ms 146776 KB Output is correct
7 Correct 221 ms 147536 KB Output is correct
8 Correct 231 ms 147364 KB Output is correct
9 Correct 401 ms 247380 KB Output is correct
10 Correct 207 ms 122620 KB Output is correct
11 Correct 395 ms 204620 KB Output is correct
12 Correct 18 ms 40280 KB Output is correct
13 Correct 18 ms 40280 KB Output is correct
14 Correct 21 ms 40368 KB Output is correct
15 Correct 19 ms 40284 KB Output is correct
16 Correct 17 ms 40284 KB Output is correct
17 Correct 16 ms 40284 KB Output is correct
18 Correct 76 ms 93524 KB Output is correct
19 Correct 76 ms 93524 KB Output is correct
20 Correct 94 ms 93496 KB Output is correct
21 Correct 72 ms 93520 KB Output is correct
22 Correct 460 ms 248912 KB Output is correct
23 Correct 590 ms 295252 KB Output is correct
24 Correct 615 ms 305280 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 173208 KB Output is correct
2 Correct 723 ms 198820 KB Output is correct
3 Correct 78 ms 93528 KB Output is correct
4 Correct 75 ms 93524 KB Output is correct
5 Execution timed out 1040 ms 272476 KB Time limit exceeded
6 Halted 0 ms 0 KB -