oj.uz

Submission #627537

# Submission time Handle Problem Language Result Execution time Memory
627537 2022-08-12T16:28:16 Z dqhungdl Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 55276 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
const int MAX = 1e5 + 5;
bool markLow[MAX];
vector<ii> g[MAX];
vector<long long> S[MAX];
vector<vector<long long>> f[MAX];

long long calcCost(int col, int L, int R) {
    int l = lower_bound(g[col].begin(), g[col].end(), ii(L, 0)) - g[col].begin();
    int r = upper_bound(g[col].begin(), g[col].end(), ii(R, 0)) - g[col].begin() - 1;
    if (l <= r)
        return S[col][r] - (l ? S[col][l - 1] : 0);
    return 0;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < M; i++) {
        g[X[i]].emplace_back(Y[i], W[i]);
        if (!Y[i])
            markLow[X[i]] = true;
    }
    for (int i = 0; i < N; i++) {
        if (!markLow[i])
            g[i].emplace_back(0, 0);
        g[i].emplace_back(N, 0);
    }
    for (int i = 0; i < N; i++) {
        sort(g[i].begin(), g[i].end());
        S[i].resize(g[i].size());
        S[i][0] = g[i][0].second;
        for (int j = 1; j < g[i].size(); j++)
            S[i][j] = S[i][j - 1] + g[i][j].second;
        f[i].resize(g[i].size(), vector<long long>(2));
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < g[i].size(); j++) {
            if (i > 1) {
                for (int t = 0; t < g[i - 2].size(); t++) {
                    long long tmp = f[i - 2][t][1] + calcCost(i - 1, 0, max(g[i - 2][t].first, g[i][j].first));
                    f[i][j][0] = max(f[i][j][0], tmp);
                    f[i][j][1] = max(f[i][j][1], tmp);
                }
            } else {
                long long tmp = calcCost(0, 0, g[i][j].first);
                f[i][j][0] = max(f[i][j][0], tmp);
                f[i][j][1] = max(f[i][j][1], tmp);
            }
            for (int t = 0; t < g[i - 1].size(); t++) {
                if (g[i - 1][t].first <= g[i][j].first) {
                    f[i][j][0] = max(f[i][j][0], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
                    f[i][j][1] = max(f[i][j][1], f[i - 1][t][0] + calcCost(i - 1, g[i - 1][t].first, g[i][j].first));
                }
                if (g[i - 1][t].first >= g[i][j].first)
                    f[i][j][1] = max(f[i][j][1], f[i - 1][t][1] + calcCost(i, g[i][j].first, g[i - 1][t].first));
            }
        }
    }
    long long rs = 0;
    for (int j = 0; j < f[N - 1].size(); j++)
        rs = max({rs, f[N - 1][j][0], f[N - 1][j][1]});
    return rs;
}

//int main() {
//    freopen("../_input", "r", stdin);
//    int N, M;
//    assert(2 == scanf("%d %d", &N, &M));
//
//    std::vector<int> X(M), Y(M), W(M);
//    for (int i = 0; i < M; ++i) {
//        assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
//    }
//
//    long long result = max_weights(N, M, X, Y, W);
//    printf("%lld\n", result);
//    return 0;
//}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int j = 1; j < g[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
fish.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < g[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
fish.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 for (int t = 0; t < g[i - 2].size(); t++) {
      |                                 ~~^~~~~~~~~~~~~~~~~
fish.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int t = 0; t < g[i - 1].size(); t++) {
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int j = 0; j < f[N - 1].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 31772 KB Output is correct
2 Correct 132 ms 35656 KB Output is correct
3 Correct 58 ms 26124 KB Output is correct
4 Correct 56 ms 26232 KB Output is correct
5 Correct 292 ms 54352 KB Output is correct
6 Correct 430 ms 55276 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Execution timed out 1072 ms 39436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26196 KB Output is correct
2 Correct 49 ms 26084 KB Output is correct
3 Correct 68 ms 25608 KB Output is correct
4 Correct 68 ms 27064 KB Output is correct
5 Correct 96 ms 28496 KB Output is correct
6 Correct 98 ms 28504 KB Output is correct
7 Correct 84 ms 28488 KB Output is correct
8 Correct 86 ms 28492 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 7 ms 7508 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 7 ms 7508 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 17 ms 7508 KB Output is correct
17 Execution timed out 1086 ms 11712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7252 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 7 ms 7508 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 5 ms 7380 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 17 ms 7508 KB Output is correct
17 Execution timed out 1086 ms 11712 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26196 KB Output is correct
2 Correct 49 ms 26084 KB Output is correct
3 Correct 68 ms 25608 KB Output is correct
4 Correct 68 ms 27064 KB Output is correct
5 Correct 96 ms 28496 KB Output is correct
6 Correct 98 ms 28504 KB Output is correct
7 Correct 84 ms 28488 KB Output is correct
8 Correct 86 ms 28492 KB Output is correct
9 Correct 115 ms 35208 KB Output is correct
10 Correct 100 ms 22524 KB Output is correct
11 Correct 163 ms 37608 KB Output is correct
12 Correct 4 ms 7376 KB Output is correct
13 Correct 4 ms 7252 KB Output is correct
14 Correct 4 ms 7252 KB Output is correct
15 Correct 3 ms 7252 KB Output is correct
16 Correct 4 ms 7252 KB Output is correct
17 Correct 4 ms 7356 KB Output is correct
18 Correct 47 ms 26104 KB Output is correct
19 Correct 52 ms 26072 KB Output is correct
20 Correct 46 ms 26060 KB Output is correct
21 Correct 46 ms 26048 KB Output is correct
22 Correct 127 ms 35396 KB Output is correct
23 Correct 204 ms 44964 KB Output is correct
24 Correct 189 ms 45468 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 31772 KB Output is correct
2 Correct 132 ms 35656 KB Output is correct
3 Correct 58 ms 26124 KB Output is correct
4 Correct 56 ms 26232 KB Output is correct
5 Correct 292 ms 54352 KB Output is correct
6 Correct 430 ms 55276 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Execution timed out 1072 ms 39436 KB Time limit exceeded
9 Halted 0 ms 0 KB -