oj.uz

Submission #1038461

# Submission time Handle Problem Language Result Execution time Memory
1038461 2024-07-29T20:09:25 Z Marco_Escandon Catfish Farm (IOI22_fish) C++17
3 / 100
 102 ms 43344 KB 
#include<bits/stdc++.h>
using namespace std;
#include "fish.h"
typedef long long ll;
#define x first
#define y second
long long max_weights(int n, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> w) {
    vector<vector<pair<ll,ll>>>  cad(n+1);
    vector<vector<ll>>  sol(n+1),sol2(n+1);
    for(int i=0; i<X.size(); i++)
        cad[X[i]+1].push_back({Y[i]+1,w[i]});
    for(int i=0; i<cad.size(); i++)
    {
        cad[i].push_back({0,0});
        sort(cad[i].begin(),cad[i].end());
        cad[i].push_back({1e9,0});
        for(int j=1; j<cad[i].size(); j++)
            cad[i][j].y+=cad[i][j-1].y;
        sol[i].resize(cad[i].size());
        sol2[i].resize(cad[i].size());
    }
    sol[0][0]=0;
    sol[0][1]=0;
    sol2[0][0]=0;
    sol2[0][1]=0;
    for(int i=1; i<sol.size(); i++)
    {
        ll p=0;
        for(int j=0; j<sol[i].size(); j++)
        {
            while(p<cad[i-1].size()&&cad[i-1][p]<=cad[i][j]) p++;
            p--;
            sol[i][j]=max(sol[i][j],sol2[i-1][p]+cad[i-1][p].y);
            if(i>=3)
            sol[i][j]=max(sol[i][j],sol[i-2].back()+cad[i-1].back().y);
        }
        for(int j=0; j<sol[i].size(); j++)
        {
            sol2[i][j]=sol[i][j];
            if(j>=1)
            {
                sol2[i][j]=max(sol2[i][j],sol2[i][j-1]);    
                sol[i][j]=max(sol[i][j],sol[i][j-1]);    
            }
        }
    }
    return sol.back().back();
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0; i<X.size(); i++)
      |                  ~^~~~~~~~~
fish.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0; i<cad.size(); i++)
      |                  ~^~~~~~~~~~~
fish.cpp:17:23: 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]
   17 |         for(int j=1; j<cad[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~
fish.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=1; i<sol.size(); i++)
      |                  ~^~~~~~~~~~~
fish.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int j=0; j<sol[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~
fish.cpp:31:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while(p<cad[i-1].size()&&cad[i-1][p]<=cad[i][j]) p++;
      |                   ~^~~~~~~~~~~~~~~~
fish.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j=0; j<sol[i].size(); j++)
      |                      ~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23232 KB Output is correct
2 Correct 45 ms 25536 KB Output is correct
3 Correct 19 ms 18268 KB Output is correct
4 Correct 22 ms 18264 KB Output is correct
5 Correct 98 ms 41132 KB Output is correct
6 Correct 102 ms 43344 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 60 ms 28196 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18264 KB Output is correct
2 Incorrect 19 ms 18268 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18264 KB Output is correct
2 Incorrect 19 ms 18268 KB 1st lines differ - on the 1st token, expected: '882019', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23232 KB Output is correct
2 Correct 45 ms 25536 KB Output is correct
3 Correct 19 ms 18268 KB Output is correct
4 Correct 22 ms 18264 KB Output is correct
5 Correct 98 ms 41132 KB Output is correct
6 Correct 102 ms 43344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 60 ms 28196 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
9 Halted 0 ms 0 KB -