oj.uz

답안 #632830

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
632830 2022-08-20T22:03:05 Z Olympia 메기 농장 (IOI22_fish) C++17
44 / 100
 843 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 += 2;
    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(dp[i - 1][cur][1], dp[i - 1][cur][2]));
            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 765 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 843 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 17492 KB Output is correct
2 Correct 14 ms 17492 KB Output is correct
3 Correct 45 ms 21972 KB Output is correct
4 Correct 32 ms 21760 KB Output is correct
5 Correct 87 ms 29264 KB Output is correct
6 Correct 88 ms 29252 KB Output is correct
7 Correct 108 ms 29760 KB Output is correct
8 Correct 101 ms 29752 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 1 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 368 KB Output is correct
10 Correct 2 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 0 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 1 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 368 KB Output is correct
10 Correct 2 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 0 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 36 ms 7884 KB Output is correct
18 Correct 42 ms 9092 KB Output is correct
19 Correct 33 ms 8944 KB Output is correct
20 Correct 32 ms 8908 KB Output is correct
21 Correct 28 ms 7372 KB Output is correct
22 Correct 66 ms 14676 KB Output is correct
23 Correct 13 ms 4180 KB Output is correct
24 Correct 21 ms 6708 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 8 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 1 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 368 KB Output is correct
10 Correct 2 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 0 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 36 ms 7884 KB Output is correct
18 Correct 42 ms 9092 KB Output is correct
19 Correct 33 ms 8944 KB Output is correct
20 Correct 32 ms 8908 KB Output is correct
21 Correct 28 ms 7372 KB Output is correct
22 Correct 66 ms 14676 KB Output is correct
23 Correct 13 ms 4180 KB Output is correct
24 Correct 21 ms 6708 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 8 ms 4052 KB Output is correct
27 Correct 258 ms 283132 KB Output is correct
28 Correct 234 ms 45368 KB Output is correct
29 Correct 634 ms 319884 KB Output is correct
30 Incorrect 624 ms 320332 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 13 ms 17492 KB Output is correct
2 Correct 14 ms 17492 KB Output is correct
3 Correct 45 ms 21972 KB Output is correct
4 Correct 32 ms 21760 KB Output is correct
5 Correct 87 ms 29264 KB Output is correct
6 Correct 88 ms 29252 KB Output is correct
7 Correct 108 ms 29760 KB Output is correct
8 Correct 101 ms 29752 KB Output is correct
9 Runtime error 761 ms 2097152 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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