oj.uz

답안 #632827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632827 2022-08-20T21:58:23 Z Olympia 메기 농장 (IOI22_fish) C++17
44 / 100
 832 ms 2097152 KB 
#include <bits/stdc++.h>
//#include <fish.h>
using namespace std;
int64_t max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < X.size(); i++) {
        X[i]++;
    }
    int my = 0;
    for (int y: Y) {
        my = max(my, y);
    }
    my ++;
    vector<pair<int,int64_t> > vec[N + 10];
    map<int,int64_t> s[N + 10];
    for (int i = 0; i < X.size(); i++) {
        vec[X[i]].push_back(make_pair(Y[i], W[i]));
        s[X[i]][Y[i]] = W[i];
    }
    int64_t pref[N + 10][my + 2];
    for (int i = 0; i <= N + 9; i++) {
        pref[i][0] = 0;
        for (int j = 1; j <= my + 1; j++) {
            pref[i][j] = pref[i][j - 1];
            if (s[i].count(j - 1)) pref[i][j] += s[i][j - 1];
        }
    }
    int64_t dp[N + 1][my + 1][3];
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= my; j++) {
            for (int d = 0; d < 3; d++) {
                dp[i][j][d] = -1e17;
            }
        }
    }
    dp[0][0][0] = 0;
    //0 --> stagnant
    //1 --> increasing
    //2 --> decreasing
    for (int i = 1; i <= N; i++) {
        for (int p = 0; p <= my; p++) {
            dp[i][0][0] = max(dp[i][0][0], dp[i - 1][p][0]);
        }
        int64_t myMax1 = -1e17;
        int64_t myMax2 = dp[i - 1][0][0] - pref[i - 1][0];
        for (int cur = 1; cur <= my; cur++) {
            dp[i][cur][0] = max(dp[i][cur][0], max(max(dp[i - 1][cur][1], dp[i - 1][cur][2]), dp[i - 1][cur][0]));
            myMax1 = max(myMax1, dp[i - 1][cur][1] - pref[i][cur] - pref[i - 1][cur]);
            dp[i][cur][1] = max(dp[i][cur][1], myMax1 + pref[i + 1][cur] + pref[i - 1][cur]);
            for (int d = 1; d <= 2; d++) {
                myMax2 = max(myMax2, dp[i - 1][cur][0] - pref[i - 1][cur]);
                dp[i][cur][d] = max(dp[i][cur][d], myMax2 + pref[i - 1][cur] + pref[i + 1][cur]);
            }
        }
        int64_t myMax3 = -1e17, myMax4 = -1e17;
        for (int cur = my; cur >= 1; cur--) {
            myMax4 = max(myMax4, dp[i - 1][cur][2]);
            dp[i][cur][2] = max(dp[i][cur][2], myMax4 - pref[i][cur] + pref[i + 1][cur]);
            for (int d = 1; d <= 2; d++) {
                myMax3 = max(myMax3, dp[i - 1][cur][0]);
                dp[i][cur][d] = max(dp[i][cur][d], myMax3 + pref[i + 1][cur]);
            }
        }
    }
    int64_t myMax = 0;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= my; j++) {
            for (int d = 0; d <= 2; d++) {
                myMax = max(myMax, dp[i][j][d]);
            }
        }
    }
    return myMax;
}

Compilation message

fish.cpp: In function 'int64_t max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:5:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~
fish.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < X.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 768 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 832 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14292 KB Output is correct
2 Correct 11 ms 14376 KB Output is correct
3 Correct 46 ms 19892 KB Output is correct
4 Correct 31 ms 18724 KB Output is correct
5 Correct 96 ms 26172 KB Output is correct
6 Correct 93 ms 26828 KB Output is correct
7 Correct 85 ms 26900 KB Output is correct
8 Correct 90 ms 26812 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 3156 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 35 ms 8464 KB Output is correct
18 Correct 34 ms 9036 KB Output is correct
19 Correct 33 ms 8900 KB Output is correct
20 Correct 31 ms 8808 KB Output is correct
21 Correct 28 ms 7368 KB Output is correct
22 Correct 71 ms 14624 KB Output is correct
23 Correct 11 ms 4180 KB Output is correct
24 Correct 23 ms 6652 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 9 ms 4052 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 3 ms 3156 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 35 ms 8464 KB Output is correct
18 Correct 34 ms 9036 KB Output is correct
19 Correct 33 ms 8900 KB Output is correct
20 Correct 31 ms 8808 KB Output is correct
21 Correct 28 ms 7368 KB Output is correct
22 Correct 71 ms 14624 KB Output is correct
23 Correct 11 ms 4180 KB Output is correct
24 Correct 23 ms 6652 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 9 ms 4052 KB Output is correct
27 Correct 274 ms 282956 KB Output is correct
28 Correct 240 ms 45244 KB Output is correct
29 Correct 577 ms 319820 KB Output is correct
30 Incorrect 613 ms 320428 KB 1st lines differ - on the 1st token, expected: '102439236138254', found: '102426281544023'
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14292 KB Output is correct
2 Correct 11 ms 14376 KB Output is correct
3 Correct 46 ms 19892 KB Output is correct
4 Correct 31 ms 18724 KB Output is correct
5 Correct 96 ms 26172 KB Output is correct
6 Correct 93 ms 26828 KB Output is correct
7 Correct 85 ms 26900 KB Output is correct
8 Correct 90 ms 26812 KB Output is correct
9 Runtime error 776 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 768 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -