oj.uz

답안 #732682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732682 2023-04-29T07:28:47 Z math_rabbit_1028 메기 농장 (IOI22_fish) C++17
35 / 100
 1000 ms 77260 KB 
#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

long long zero[101010], full[101010];
vector< pair<int, long long> > ylist[101010];
vector< long long > sum[101010], dp[2][101010];

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    for (int i = 0; i < M; i++) {
        X[i] += 1;
        Y[i] += 1;
        ylist[X[i]].push_back({Y[i], 0});
        ylist[X[i] - 1].push_back({Y[i], 0});
        ylist[X[i] + 1].push_back({Y[i], 0});
    }

    for (int i = 0; i <= N + 1; i++) {
        ylist[i].push_back({0, 0});
        ylist[i].push_back({N, 0});
        sort(ylist[i].begin(), ylist[i].end());
        ylist[i].erase(unique(ylist[i].begin(), ylist[i].end()), ylist[i].end());
    }

    for (int i = 0; i < M; i++) {
        int idx = lower_bound(ylist[X[i]].begin(), ylist[X[i]].end(), make_pair(Y[i], 0LL)) - ylist[X[i]].begin();
        ylist[X[i]][idx].second = W[i];
    }

    for (int i = 0; i <= N + 1; i++) {
        sum[i].push_back(0);
        for (int j = 1; j < ylist[i].size(); j++) {
            sum[i].push_back(sum[i].back() + ylist[i][j].second);
        }
    }

    for (int i = 0; i <= N + 1; i++) {
        for (int j = 0; j < ylist[i].size(); j++) dp[0][i].push_back(0);
        for (int j = 0; j < ylist[i].size(); j++) dp[1][i].push_back(0);
    }
    for (int j = 1; j < ylist[0].size() - 1; j++) dp[0][0][j] = -1e18;
    for (int j = 1; j < ylist[0].size() - 1; j++) dp[1][0][j] = -1e18;
    full[0] = -1e18;
    for (int i = 2; i <= N + 1; i++) {
        vector<int> all;
        for (int i = 0; i <= N; i++) all.push_back(i);
        //for (int t = 0; t < ylist[i - 2].size(); t++) all.push_back(ylist[i - 2][t].first);
        //for (int t = 0; t < ylist[i - 1].size(); t++) all.push_back(ylist[i - 1][t].first);
        //for (int t = 0; t < ylist[i].size(); t++) all.push_back(ylist[i][t].first);
        //sort(all.begin(), all.end());
        //all.erase(unique(all.begin(), all.end()), all.end());

        int j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            zero[i] = max(zero[i], dp[1][i - 1][k] + sum[i][j]);
        }
        zero[i] = max(zero[i], zero[i - 1]);
        zero[i] = max(zero[i], full[i - 1] + sum[i][ylist[i].size() - 1]);

        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            full[i] = max(full[i], dp[0][i - 1][k] + sum[i - 1][ylist[i - 1].size() - 1] - sum[i - 1][k]);
        }
        full[i] = max(full[i], full[i - 1]);
        full[i] = max(full[i], zero[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        full[i] = max(full[i], full[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            full[i] = max(full[i], dp[1][i - 2][l] + sum[i - 1][ylist[i - 1].size() - 1]);
        }

        long long val0 = 0, val1 = 0;
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            val0 = max(val0, dp[0][i - 1][k] - sum[i - 1][k]);
            val1 = max(val1, dp[1][i - 1][k] + sum[i][j]);
        }
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            dp[0][i][j] = max(dp[0][i][j], val0 + sum[i - 1][k]);
            dp[1][i][j] = max(dp[1][i][j], val1 - sum[i][j]);
            dp[1][i][j] = max(dp[1][i][j], full[i - 1] + sum[i][ylist[i].size() - 1] - sum[i][j]);
            dp[0][i][j] = max(dp[0][i][j], zero[i - 2] + sum[i - 1][k]);
            dp[0][i][j] = max(dp[0][i][j], full[i - 2] + sum[i - 1][ylist[i - 1].size() - 1]);
        }
        long long val2 = 0;
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            if (ylist[i - 2][l].first != all[t]) continue;
            val2 = max(val2, dp[1][i - 2][l]);
            dp[0][i][j] = max(dp[0][i][j], val2 + sum[i - 1][k]);
        }
        long long val3 = 0;
        j = 0, k = 0, l = 0;
        for (int t = 1; t < all.size() - 1; t++) {
            while (ylist[i][j] < make_pair(all[t], 0LL)) j++;
            while (ylist[i - 1][k] < make_pair(all[t], 0LL)) k++;
            while (ylist[i - 2][l] < make_pair(all[t], 0LL)) l++;
            if (ylist[i - 2][l].first != all[t]) continue;
            val3 = max(val3, dp[1][i - 2][l] + sum[i - 1][k]);
            dp[0][i][j] = max(dp[0][i][j], val3);
        }
    }
    long long res = 0;
    res = zero[N + 1];
    return res;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j = 1; j < ylist[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int j = 0; j < ylist[i].size(); j++) dp[0][i].push_back(0);
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < ylist[i].size(); j++) dp[1][i].push_back(0);
      |                         ~~^~~~~~~~~~~~~~~~~
fish.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 1; j < ylist[0].size() - 1; j++) dp[0][0][j] = -1e18;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int j = 1; j < ylist[0].size() - 1; j++) dp[1][0][j] = -1e18;
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
fish.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~
fish.cpp:114:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for (int t = 1; t < all.size() - 1; t++) {
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 34780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1089 ms 42928 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 24776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9796 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9796 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 9 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9940 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 8 ms 9940 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9796 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9796 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 9 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9940 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 8 ms 9940 KB Output is correct
15 Correct 8 ms 9812 KB Output is correct
16 Correct 7 ms 10068 KB Output is correct
17 Correct 38 ms 16220 KB Output is correct
18 Correct 35 ms 15676 KB Output is correct
19 Correct 33 ms 15556 KB Output is correct
20 Correct 35 ms 15236 KB Output is correct
21 Correct 35 ms 15076 KB Output is correct
22 Correct 64 ms 20428 KB Output is correct
23 Correct 17 ms 11492 KB Output is correct
24 Correct 30 ms 14756 KB Output is correct
25 Correct 9 ms 9940 KB Output is correct
26 Correct 15 ms 11428 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9796 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9796 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 9 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 8 ms 9940 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 8 ms 9940 KB Output is correct
15 Correct 8 ms 9812 KB Output is correct
16 Correct 7 ms 10068 KB Output is correct
17 Correct 38 ms 16220 KB Output is correct
18 Correct 35 ms 15676 KB Output is correct
19 Correct 33 ms 15556 KB Output is correct
20 Correct 35 ms 15236 KB Output is correct
21 Correct 35 ms 15076 KB Output is correct
22 Correct 64 ms 20428 KB Output is correct
23 Correct 17 ms 11492 KB Output is correct
24 Correct 30 ms 14756 KB Output is correct
25 Correct 9 ms 9940 KB Output is correct
26 Correct 15 ms 11428 KB Output is correct
27 Correct 213 ms 11068 KB Output is correct
28 Correct 158 ms 35520 KB Output is correct
29 Correct 431 ms 48076 KB Output is correct
30 Incorrect 519 ms 77260 KB 1st lines differ - on the 1st token, expected: '102439236138254', found: '102440153599307'
31 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 24776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 34780 KB Time limit exceeded
2 Halted 0 ms 0 KB -