oj.uz

Submission #626806

# Submission time Handle Problem Language Result Execution time Memory
626806 2022-08-11T20:15:43 Z Kaitokid Catfish Farm (IOI22_fish) C++17
61 / 100
 1000 ms 38680 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mx;
ll dp2[309][309][2];

ll sum[3009][3009];
ll go5(int x,int lst,int u)
{
    if(x==mx)return 0;
    if(dp2[x][lst][u]!=-1)return dp2[x][lst][u];
    for(int i=0;i<=mx;i++)
    {
        ll d=0;
        if(u==0 && i>lst) d=sum[x-1][i]-sum[x-1][lst];
        dp2[x][lst][u]=max(dp2[x][lst][u],d+go5(x+1,i,0));
        if(i<lst)d+=sum[x][lst]-sum[x][i];
        dp2[x][lst][u]=max(dp2[x][lst][u],d+go5(x+1,i,1));
    }
    return dp2[x][lst][u];
}
ll max_weights5(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
    mx=N;
    for(int i=0;i<M;i++)sum[X[i]][Y[i]+1]+=W[i];
    for(int i=0;i<N;i++)
        for(int j=1;j<=N;j++)sum[i][j]+=sum[i][j-1];
    memset(dp2,-1,sizeof dp2);
    ll ans=0;
    for(int i=0;i<=N;i++)
       ans=max(ans,go5(1,i,0));
       return ans;
}
vector<int>g[100009],f[300009];
ll dp[100009][3][2];
ll go7(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+go7(x+1,i,0));

        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+go7(x+1,i,1));
    }
    return dp[x][lst][u];
}
ll max_weights7(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,go7(1,i,0));
       return ans;
}
ll max_weights1(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
   ll ans=0;
   for(int i=0;i<M;i++)ans+=W[i];
   return ans;
}
ll max_weights2(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
    ll ans1=0,ans2=0;
    for(int i=0;i<M;i++)
        if(X[i]==0)ans1+=W[i];
     else ans2+=W[i];
     return max(ans1,ans2);
}
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
    if(N<=300)return  max_weights5(N,M,X,Y,W);
    bool bl1=true,bl2=true;
    for(int i=0;i<M;i++)
    {if(X[i]%2)bl1=false;
    if(X[i]>1)bl2=false;}
    if(bl1)return  max_weights1(N,M,X,Y,W);
    if(bl2)return  max_weights2(N,M,X,Y,W);
    return  max_weights7(N,M,X,Y,W);


}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12464 KB Output is correct
2 Correct 32 ms 13152 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 89 ms 20172 KB Output is correct
6 Correct 91 ms 20300 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11156 KB Output is correct
2 Incorrect 49 ms 15332 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 24 ms 31612 KB Output is correct
3 Correct 57 ms 31900 KB Output is correct
4 Correct 47 ms 32872 KB Output is correct
5 Correct 111 ms 35084 KB Output is correct
6 Correct 89 ms 35148 KB Output is correct
7 Correct 85 ms 35112 KB Output is correct
8 Correct 92 ms 35160 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 6 ms 11160 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 6 ms 11132 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 8 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 38 ms 12016 KB Output is correct
10 Correct 244 ms 13216 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 265 ms 13176 KB Output is correct
13 Correct 11 ms 11476 KB Output is correct
14 Correct 238 ms 13172 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 6 ms 11160 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 6 ms 11132 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 8 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 38 ms 12016 KB Output is correct
10 Correct 244 ms 13216 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 265 ms 13176 KB Output is correct
13 Correct 11 ms 11476 KB Output is correct
14 Correct 238 ms 13172 KB Output is correct
15 Correct 249 ms 13144 KB Output is correct
16 Correct 13 ms 11604 KB Output is correct
17 Correct 262 ms 14768 KB Output is correct
18 Correct 249 ms 14732 KB Output is correct
19 Correct 260 ms 14728 KB Output is correct
20 Correct 257 ms 14736 KB Output is correct
21 Correct 255 ms 14736 KB Output is correct
22 Correct 283 ms 16324 KB Output is correct
23 Correct 246 ms 13452 KB Output is correct
24 Correct 264 ms 14192 KB Output is correct
25 Correct 247 ms 13176 KB Output is correct
26 Correct 239 ms 13428 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11092 KB Output is correct
2 Correct 6 ms 11160 KB Output is correct
3 Correct 6 ms 11092 KB Output is correct
4 Correct 6 ms 11132 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 8 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 38 ms 12016 KB Output is correct
10 Correct 244 ms 13216 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 265 ms 13176 KB Output is correct
13 Correct 11 ms 11476 KB Output is correct
14 Correct 238 ms 13172 KB Output is correct
15 Correct 249 ms 13144 KB Output is correct
16 Correct 13 ms 11604 KB Output is correct
17 Correct 262 ms 14768 KB Output is correct
18 Correct 249 ms 14732 KB Output is correct
19 Correct 260 ms 14728 KB Output is correct
20 Correct 257 ms 14736 KB Output is correct
21 Correct 255 ms 14736 KB Output is correct
22 Correct 283 ms 16324 KB Output is correct
23 Correct 246 ms 13452 KB Output is correct
24 Correct 264 ms 14192 KB Output is correct
25 Correct 247 ms 13176 KB Output is correct
26 Correct 239 ms 13428 KB Output is correct
27 Correct 9 ms 14932 KB Output is correct
28 Execution timed out 1063 ms 25552 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 24 ms 31612 KB Output is correct
3 Correct 57 ms 31900 KB Output is correct
4 Correct 47 ms 32872 KB Output is correct
5 Correct 111 ms 35084 KB Output is correct
6 Correct 89 ms 35148 KB Output is correct
7 Correct 85 ms 35112 KB Output is correct
8 Correct 92 ms 35160 KB Output is correct
9 Correct 108 ms 35084 KB Output is correct
10 Correct 68 ms 26484 KB Output is correct
11 Correct 150 ms 38564 KB Output is correct
12 Correct 5 ms 11220 KB Output is correct
13 Correct 6 ms 11092 KB Output is correct
14 Correct 6 ms 11092 KB Output is correct
15 Correct 5 ms 11096 KB Output is correct
16 Correct 6 ms 11152 KB Output is correct
17 Correct 6 ms 11092 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 24 ms 31568 KB Output is correct
21 Correct 23 ms 31616 KB Output is correct
22 Correct 96 ms 35048 KB Output is correct
23 Correct 197 ms 38564 KB Output is correct
24 Correct 161 ms 38680 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12464 KB Output is correct
2 Correct 32 ms 13152 KB Output is correct
3 Correct 7 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 89 ms 20172 KB Output is correct
6 Correct 91 ms 20300 KB Output is correct
7 Correct 6 ms 11156 KB Output is correct
8 Incorrect 49 ms 15332 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479197388443'
9 Halted 0 ms 0 KB -