oj.uz

Submission #632023

# Submission time Handle Problem Language Result Execution time Memory
632023 2022-08-19T10:19:47 Z timreizin Catfish Farm (IOI22_fish) C++17
6 / 100
 136 ms 16236 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include "fish.h"

#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

using ll = long long;

ll solve(vector<vector<pair<int, ll>>> &fish, int n)
{
    ll res = 0;
    vector<vector<ll>> dp0(fish.size()), dp1(fish.size());
    ll sum = 0;
    for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
    for (int i = 0; i < fish.size(); ++i)
    {
        fish[i].emplace_back(n, 0);
        dp0[i].resize(fish[i].size());
        ll mx = 0;
        if (i != 0)
        {
            for (int j = 0; j < fish[i - 1].size(); ++j)
            {
                mx = max(mx, dp1[i - 1][j]);
            }
            fill(dp0[i].begin(), dp0[i].end(), mx);
            mx = 0;
        }
        for (int j = 0, k = 0; j < fish[i].size(); ++j)
        {
            if (i != 0)
            {
                while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
                {
                    mx = max(mx, dp0[i - 1][k]);
                    mx += fish[i - 1][k].second;
                    ++k;
                }
            }
            dp0[i][j] = max(mx, dp0[i][j]);
        }
        dp1 = dp0;
        if (i != 0)
        {
            ll mx = 0;
            for (int j = (int)fish[i].size() - 1, k = (int)fish[i - 1].size() - 1; j >= 0; --j)
            {
                 while (k >= 0 && fish[i - 1][k].first > fish[i][j].first)
                 {
                     mx = max(mx, dp1[i - 1][k]);
                     --k;
                 }
                mx += fish[i][j].second;
                dp1[i][j] = max(dp1[i][j], mx);
                res = max(dp1[i][j], res);
            }
        }
    }
    return res;
}

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
    vector<tuple<int, int, ll>> xyw(m);
    for (int i = 0; i < m; ++i) xyw[i] = {X[i], Y[i], W[i]};
    sort(xyw.begin(), xyw.end());
    ll res = 0;
    vector<vector<pair<int, ll>>> tos;
    int prevX = -1;
    ll sum = 0;
    vector<ll> a(n);
    for (auto [x, y, w] : xyw)
    {
        a[x] = w;
        sum += w;
        if (x > prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
            //res += solve(tos, n);
            tos.clear();
            tos.push_back(vector<pair<int, ll>>());
            prevX = x - 1;
        }
        if (x == prevX + 1)
        {
            tos.push_back(vector<pair<int, ll>>());
        }
        tos.back().emplace_back(y, w);
        prevX = x;
    }
    if (prevX != n - 1) tos.push_back(vector<pair<int, ll>>());
    res += solve(tos, n);
    //assert(res <= sum);
    return res;
}
/*
5 6
4 2 1
2 0 2
2 2 4
2 4 8
4 3 16
2 1 32
*/

/*
5 5
0 0 4
1 0 8
2 0 5
3 0 1
4 0 9
*/

Compilation message

fish.cpp: In function 'll solve(std::vector<std::vector<std::pair<int, long long int> > >&, int)':
fish.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
      |                     ~~^~~~~~~~~~~~~
fish.cpp:18:61: 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]
   18 |     for (int i = 0; i < fish.size(); ++i) for (int j = 0; j < fish[i].size(); ++j) sum += fish[i][j].second;
      |                                                           ~~^~~~~~~~~~~~~~~~
fish.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < fish.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
fish.cpp:26:31: 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]
   26 |             for (int j = 0; j < fish[i - 1].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:33:34: 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 = 0, k = 0; j < fish[i].size(); ++j)
      |                                ~~^~~~~~~~~~~~~~~~
fish.cpp:37:26: 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]
   37 |                 while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
      |                        ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6584 KB Output is correct
2 Correct 44 ms 8108 KB Output is correct
3 Correct 0 ms 980 KB Output is correct
4 Correct 0 ms 980 KB Output is correct
5 Incorrect 136 ms 16236 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44829854937734'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 12384 KB Output is correct
3 Correct 107 ms 15172 KB Output is correct
4 Correct 35 ms 6596 KB Output is correct
5 Correct 43 ms 8108 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 0 ms 212 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 37 ms 6604 KB Output is correct
13 Correct 42 ms 7996 KB Output is correct
14 Correct 36 ms 6620 KB Output is correct
15 Correct 46 ms 7356 KB Output is correct
16 Correct 37 ms 6604 KB Output is correct
17 Correct 40 ms 7352 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Incorrect 23 ms 3160 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '215560985'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 272 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 272 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 272 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 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
9 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Incorrect 23 ms 3160 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '215560985'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6584 KB Output is correct
2 Correct 44 ms 8108 KB Output is correct
3 Correct 0 ms 980 KB Output is correct
4 Correct 0 ms 980 KB Output is correct
5 Incorrect 136 ms 16236 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '44829854937734'
6 Halted 0 ms 0 KB -