oj.uz

Submission #838827

# Submission time Handle Problem Language Result Execution time Memory
838827 2023-08-27T20:04:28 Z Andrey Catfish Farm (IOI22_fish) C++17
0 / 100
 219 ms 134948 KB 
#include "fish.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

/// Bobcho tova e C grupa DP

vector<pair<long long,long long>> haha[100001];
vector<pair<long long,long long>> bruh[100001];
vector<long long> dp[100001][3];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> Y, std::vector<int> w) {
    for(long long i = 0; i < m; i++) {
        bruh[x[i]].push_back({Y[i],w[i]});
        dp[x[i]][0].push_back(0);
        dp[x[i]][1].push_back(0);
        dp[x[i]][2].push_back(0);
    }
    for(int i = 0; i <= n; i++) {
        bruh[i].push_back({n,0});
        bruh[i].push_back({n+1,0});
        bruh[i].push_back({0,0});
        sort(bruh[i].begin(),bruh[i].end());
        dp[i][0].push_back(0);
        dp[i][1].push_back(0);
        dp[i][2].push_back(0);
        dp[i][0].push_back(0);
        dp[i][1].push_back(0);
        dp[i][2].push_back(0);
        dp[i][0].push_back(0);
        dp[i][1].push_back(0);
        dp[i][2].push_back(0);
    }
    for(long long i = 0; i <= n; i++) {
        long long br = 0;
        for(long long j = 0; j < bruh[i].size(); j++) {
            haha[i].push_back({bruh[i][j].first,br});
            br+=bruh[i][j].second;
        }
    }
    int y = 0;
    for(int i = 0; i < haha[0].size(); i++) {
        while(y < haha[1].size() && haha[0][i].first > haha[1][y].first) {
            y++;
        }
        if(y > 0) {
            dp[0][0][i] = haha[1][y-1].second;
        }
    }
    long long ans = 0,z = 0,sb = 0;
    for(long long i = 1; i < n; i++) {
        y = 1;
        z = 1;
        sb = 0;
        for(long long j = 0; j < haha[i].size(); j++) {
            while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
                y++;
            }
            dp[i][2][j] = max(dp[i][2][j],dp[i-1][0][y-1]);
            dp[i][2][j] = max(dp[i][2][j],dp[i-1][1][y-1]);
        }
        for(int j = 0; j < haha[i-1].size(); j++) {
            sb = max(sb,dp[i-1][2][j]);
        }
        long long big = 0;
        y = 1;
        z = 1;
        for(long long j = 0; j < haha[i].size(); j++) {
            while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
                y++;
            }
            while(z < haha[i+1].size() && haha[i+1][z].first <= haha[i][j].first) {
                z++;
            }
            big = max(big,dp[i-1][0][y-1]-haha[i-1][y-1].second-haha[i][j].second);
            dp[i][0][j] = big+haha[i+1][z-1].second+haha[i-1][y-1].second;
        }
        big = 0;
        y = haha[i-1].size()-2;
        z = haha[i+1].size()-2;
        for(long long j = haha[i].size()-1; j >= 0; j--) {
            while(y >= 0 && haha[i-1][y].first > haha[i][j].first) {
                y--;
            }
            while(z >= 0 && haha[i+1][z].first > haha[i][j].first) {
                z--;
            }
            dp[i][1][j] = big-haha[i][j].second+haha[i+1][z+1].second;
            big = max(big,dp[i-1][0][y+1]);
        }
        big = 0;
        y = haha[i-1].size()-2;
        z = haha[i+1].size()-2;
        for(long long j = haha[i].size()-1; j >= 0; j--) {
            while(y >= 0 && haha[i-1][y].first > haha[i][j].first) {
                y--;
            }
            while(z >= 0 && haha[i+1][z].first > haha[i][j].first) {
                z--;
            }
            dp[i][1][j] = max(dp[i][1][j],big-haha[i][j].second+haha[i+1][z+1].second);
            big = max(big,dp[i-1][1][y+1]);
        }
        big = 0;
        y = 1;
        z = 1;
        for(long long j = 0; j < haha[i].size(); j++) {
            while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
                y++;
            }
            while(z < haha[i+1].size() && haha[i+1][y].first <= haha[i][j].first) {
                z++;
            }
            dp[i][0][j] = max(dp[i][0][j],sb+haha[i+1][z-1].second);
            big = max(big,dp[i-1][2][y-1]-haha[i-1][y-1].second);
            dp[i][0][j] = max(dp[i][0][j],big+haha[i-1][y-1].second);
        }
    }
    for(long long i = 0; i < dp[n-1][0].size(); i++) {
        ans = max(ans,dp[n-1][0][i]);
        ans = max(ans,dp[n-1][1][i]);
        ans = max(ans,dp[n-1][2][i]);
    }
    return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:36:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(long long j = 0; j < bruh[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
fish.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < haha[0].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
fish.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while(y < haha[1].size() && haha[0][i].first > haha[1][y].first) {
      |               ~~^~~~~~~~~~~~~~~~
fish.cpp:55:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(long long j = 0; j < haha[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
fish.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
      |                   ~~^~~~~~~~~~~~~~~~~~
fish.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = 0; j < haha[i-1].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
fish.cpp:68:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(long long j = 0; j < haha[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
fish.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
      |                   ~~^~~~~~~~~~~~~~~~~~
fish.cpp:72:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while(z < haha[i+1].size() && haha[i+1][z].first <= haha[i][j].first) {
      |                   ~~^~~~~~~~~~~~~~~~~~
fish.cpp:107:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(long long j = 0; j < haha[i].size(); j++) {
      |                              ~~^~~~~~~~~~~~~~~~
fish.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while(y < haha[i-1].size() && haha[i-1][y].first <= haha[i][j].first) {
      |                   ~~^~~~~~~~~~~~~~~~~~
fish.cpp:111:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             while(z < haha[i+1].size() && haha[i+1][y].first <= haha[i][j].first) {
      |                   ~~^~~~~~~~~~~~~~~~~~
fish.cpp:119:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(long long i = 0; i < dp[n-1][0].size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 45500 KB Output is correct
2 Correct 103 ms 49760 KB Output is correct
3 Correct 70 ms 41768 KB Output is correct
4 Correct 73 ms 41812 KB Output is correct
5 Runtime error 219 ms 134948 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 41668 KB Output is correct
2 Correct 67 ms 41732 KB Output is correct
3 Incorrect 117 ms 40644 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26860403425264'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 11988 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 41668 KB Output is correct
2 Correct 67 ms 41732 KB Output is correct
3 Incorrect 117 ms 40644 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26860403425264'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 45500 KB Output is correct
2 Correct 103 ms 49760 KB Output is correct
3 Correct 70 ms 41768 KB Output is correct
4 Correct 73 ms 41812 KB Output is correct
5 Runtime error 219 ms 134948 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -