oj.uz

Submission #626596

# Submission time Handle Problem Language Result Execution time Memory
626596 2022-08-11T14:52:16 Z Kaitokid Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 30260 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mx;
ll dp[100009][3][2];
vector<int>g[100009],f[100009];
ll go(int x,int lst,int u)
{
    if(x==mx)return 0;
    if(dp[x][lst][u]!=-1)return dp[x][lst][u];
    for(int i=0;i<g[x].size();i++)
    {
        ll d=0;
        if(u==0 && g[x][i]>g[x-1][lst])
           {
                for(int j=0;j<g[x-1].size();j++)
                if(g[x-1][j]>=g[x-1][lst] && g[x-1][j]<g[x][i])d+=f[x-1][j];
           }
        dp[x][lst][u]=max(dp[x][lst][u],d+go(x+1,i,0));
        if(i<lst)
        {
            for(int j=0;j<g[x].size();j++)
                 if(g[x][j]<g[x-1][lst] && g[x][j]>=g[x][i])d+=f[x][j];
        }

        dp[x][lst][u]=max(dp[x][lst][u],d+go(x+1,i,1));
    }
    return dp[x][lst][u];
}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
    mx=N;
    for(int i=0;i<M;i++)
    {
        g[X[i]].push_back(Y[i]+1);
        f[X[i]].push_back(W[i]);
    }
    for(int i=0;i<N;i++)
    {
        g[i].push_back(N+1);f[i].push_back(0);
    }
    memset(dp,-1,sizeof dp);
    ll ans=0;
    for(int i=0;i<g[0].size();i++)
       ans=max(ans,go(1,i,0));
       return ans;
}

Compilation message

fish.cpp: In function 'll go(int, int, int)':
fish.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<g[x].size();i++)
      |                 ~^~~~~~~~~~~~
fish.cpp:16:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |                 for(int j=0;j<g[x-1].size();j++)
      |                             ~^~~~~~~~~~~~~~
fish.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for(int j=0;j<g[x].size();j++)
      |                         ~^~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<g[0].size();i++)
      |                 ~^~~~~~~~~~~~
fish.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   44 |     for(int i=0;i<g[0].size();i++)
      |     ^~~
fish.cpp:46:8: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |        return ans;
      |        ^~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 27720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1093 ms 30260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 26904 KB Output is correct
2 Incorrect 20 ms 26908 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 7 ms 9688 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 5 ms 9684 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 7 ms 9688 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 5 ms 9684 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 7 ms 9688 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Incorrect 5 ms 9684 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 21 ms 26904 KB Output is correct
2 Incorrect 20 ms 26908 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 Execution timed out 1089 ms 27720 KB Time limit exceeded
2 Halted 0 ms 0 KB -