oj.uz

Submission #626854

# Submission time Handle Problem Language Result Execution time Memory
626854 2022-08-11T21:45:08 Z ionan6ix Catfish Farm (IOI22_fish) C++17
9 / 100
 82 ms 7264 KB 
#include "fish.h"

#include <vector>
#include<algorithm>
using namespace std;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    bool flag = true;

    for(auto it:X)
        if(it%2)
        {
            flag = false;
            break;
        }

    if(flag)
    {
        long long sol = 0;
        for(auto it:W)
            sol+=it;

        return sol;
    }

    flag = true;

    for(auto it:X)
        if(it>1)
        {
            flag = false;
            break;
        }

    if(flag)
    {
        std::vector<pair<int,int> > y0;
        std::vector<pair<int,int> > y1;

        int sz = X.size();

        for(int i=0;i<M;i++)
            if(X[i]==0) y0.emplace_back(Y[i],W[i]);
                else y1.emplace_back(Y[i],W[i]);

        std::sort(y0.begin(),y0.end());
        std::sort(y1.begin(),y1.end());

        if(N==2)
        {
            //efectiv...

            long long sum0=0LL;
            long long sum1=0LL;

            for(auto it:y0)
                sum0+=1LL*it.second;

            for(auto it:y1)
                sum1+=1LL*it.second;

            return max(sum0,sum1);
        }
        long long sol = 0LL;
        long long sum = 0LL;

        for(auto it:y1)
            sum += 1LL*it.second;

        sol = sum;

        /**
         * Pana la un anumit punct luam din 0, apoi din 1
         */

        int pnt0 = -1;
        int pnt1 = 0;
        long long sum0 = 0;
        for(int i=0;i<(int)y0.size();i++)
        {
            pnt0++;
            sum0 += 1LL * y0[i].second;

            while(pnt1<(int)y1.size() && y1[pnt1].first<=y0[i].first)
            {
                sum -= 1LL * y1[pnt1].second;
                pnt1++;
            }
            sol = max(sol,sum+sum0);
        }
        sol = max(sol,sum+sum0);
        sum0 = 0LL;
        for(auto it:y0)
            sum0+=1LL*it.second;

        sol = max(sol,sum0);


        return sol;
    }

    flag = true;

    for(auto it:Y)
        if(it!=0)
        {
            flag = false;
            break;
        }

    if(flag)
    {

        vector<vector<int> > dp;

        dp.resize(N+5);

        for(int i = 0;i<N;i++)
            dp[i].resize(2);

        dp[0][0] = 0;
        dp[0][1] = 0;

        vector<int> repr;
        repr.resize(N+5);

        for(int i = 0;i<M;i++)
            repr[X[i]] = W[i];

        dp[1][1] = repr[0];
        dp[1][0] = repr[1];

        for(int i=2;i<N;i++)
        {
            dp[i][0] = max(dp[i-1][1]+repr[i],dp[i-1][0]);
            dp[i][1] = max(dp[i-2][0],max(dp[i-2][1],dp[i-2][0]+repr[i-1]));
        }

        return max(dp[N-1][0],dp[N-1][1]);
    }
    return 0;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:13: warning: unused variable 'sz' [-Wunused-variable]
   42 |         int sz = X.size();
      |             ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2132 KB Output is correct
2 Correct 26 ms 2644 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 82 ms 7260 KB Output is correct
6 Correct 79 ms 7264 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 62 ms 5684 KB Output is correct
3 Correct 68 ms 6724 KB Output is correct
4 Correct 29 ms 2136 KB Output is correct
5 Correct 37 ms 2624 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 26 ms 3304 KB Output is correct
13 Correct 33 ms 3760 KB Output is correct
14 Correct 29 ms 3060 KB Output is correct
15 Correct 32 ms 3368 KB Output is correct
16 Correct 27 ms 3160 KB Output is correct
17 Correct 30 ms 3272 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2132 KB Output is correct
2 Correct 26 ms 2644 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 82 ms 7260 KB Output is correct
6 Correct 79 ms 7264 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 62 ms 5684 KB Output is correct
9 Correct 68 ms 6724 KB Output is correct
10 Correct 29 ms 2136 KB Output is correct
11 Correct 37 ms 2624 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 26 ms 3304 KB Output is correct
19 Correct 33 ms 3760 KB Output is correct
20 Correct 29 ms 3060 KB Output is correct
21 Correct 32 ms 3368 KB Output is correct
22 Correct 27 ms 3160 KB Output is correct
23 Correct 30 ms 3272 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 8 ms 6100 KB Output is correct
26 Incorrect 23 ms 6944 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '2147479351'
27 Halted 0 ms 0 KB -