oj.uz

Submission #626808

# Submission time Handle Problem Language Result Execution time Memory
626808 2022-08-11T20:27:03 Z Kaitokid Catfish Farm (IOI22_fish) C++17
67 / 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;
}
int a[2][200009];
ll max_weights2(int N,int M,vector<int>X,vector<int>Y,vector<int>W)
{
    for(int i=0;i<M;i++)
      a[X[i]][Y[i]]+=W[i];
      ll ans=0,mx=0;
      for(int i=0;i<N;i++)ans+=a[1][i];
      mx=ans;
      for(int i=0;i<N;i++)
      {
          ans-=a[1][i];
          ans+=a[0][i];
          mx=max(ans,mx);
      }
     return mx;
}
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;
      |        ^~~~~~
fish.cpp: In function 'll max_weights2(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for(int i=0;i<M;i++)
      |     ^~~
fish.cpp:87:7: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   87 |       ll ans=0,mx=0;
      |       ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12452 KB Output is correct
2 Correct 30 ms 13224 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 90 ms 20260 KB Output is correct
6 Correct 94 ms 20260 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11092 KB Output is correct
2 Correct 53 ms 16100 KB Output is correct
3 Correct 71 ms 17560 KB Output is correct
4 Correct 28 ms 12448 KB Output is correct
5 Correct 31 ms 13200 KB Output is correct
6 Correct 5 ms 11092 KB Output is correct
7 Correct 5 ms 11208 KB Output is correct
8 Correct 5 ms 11092 KB Output is correct
9 Correct 5 ms 11092 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 28 ms 12852 KB Output is correct
13 Correct 32 ms 13576 KB Output is correct
14 Correct 27 ms 12876 KB Output is correct
15 Correct 31 ms 13216 KB Output is correct
16 Correct 27 ms 12840 KB Output is correct
17 Correct 30 ms 13204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 22 ms 31552 KB Output is correct
3 Correct 52 ms 31688 KB Output is correct
4 Correct 51 ms 32800 KB Output is correct
5 Correct 104 ms 35152 KB Output is correct
6 Correct 94 ms 35128 KB Output is correct
7 Correct 88 ms 35148 KB Output is correct
8 Correct 96 ms 35116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11136 KB Output is correct
2 Correct 7 ms 11180 KB Output is correct
3 Correct 7 ms 11208 KB Output is correct
4 Correct 5 ms 11092 KB Output is correct
5 Correct 6 ms 11104 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 37 ms 11988 KB Output is correct
10 Correct 242 ms 13204 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 250 ms 13164 KB Output is correct
13 Correct 10 ms 11476 KB Output is correct
14 Correct 239 ms 13156 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11136 KB Output is correct
2 Correct 7 ms 11180 KB Output is correct
3 Correct 7 ms 11208 KB Output is correct
4 Correct 5 ms 11092 KB Output is correct
5 Correct 6 ms 11104 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 37 ms 11988 KB Output is correct
10 Correct 242 ms 13204 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 250 ms 13164 KB Output is correct
13 Correct 10 ms 11476 KB Output is correct
14 Correct 239 ms 13156 KB Output is correct
15 Correct 255 ms 13148 KB Output is correct
16 Correct 10 ms 11560 KB Output is correct
17 Correct 265 ms 14768 KB Output is correct
18 Correct 258 ms 14720 KB Output is correct
19 Correct 257 ms 14796 KB Output is correct
20 Correct 253 ms 14596 KB Output is correct
21 Correct 253 ms 14736 KB Output is correct
22 Correct 270 ms 16308 KB Output is correct
23 Correct 258 ms 13436 KB Output is correct
24 Correct 245 ms 14248 KB Output is correct
25 Correct 249 ms 13180 KB Output is correct
26 Correct 243 ms 13420 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11136 KB Output is correct
2 Correct 7 ms 11180 KB Output is correct
3 Correct 7 ms 11208 KB Output is correct
4 Correct 5 ms 11092 KB Output is correct
5 Correct 6 ms 11104 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 7 ms 11092 KB Output is correct
8 Correct 6 ms 11152 KB Output is correct
9 Correct 37 ms 11988 KB Output is correct
10 Correct 242 ms 13204 KB Output is correct
11 Correct 36 ms 11988 KB Output is correct
12 Correct 250 ms 13164 KB Output is correct
13 Correct 10 ms 11476 KB Output is correct
14 Correct 239 ms 13156 KB Output is correct
15 Correct 255 ms 13148 KB Output is correct
16 Correct 10 ms 11560 KB Output is correct
17 Correct 265 ms 14768 KB Output is correct
18 Correct 258 ms 14720 KB Output is correct
19 Correct 257 ms 14796 KB Output is correct
20 Correct 253 ms 14596 KB Output is correct
21 Correct 253 ms 14736 KB Output is correct
22 Correct 270 ms 16308 KB Output is correct
23 Correct 258 ms 13436 KB Output is correct
24 Correct 245 ms 14248 KB Output is correct
25 Correct 249 ms 13180 KB Output is correct
26 Correct 243 ms 13420 KB Output is correct
27 Correct 8 ms 14932 KB Output is correct
28 Execution timed out 1079 ms 25288 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 9684 KB Output is correct
2 Correct 22 ms 31552 KB Output is correct
3 Correct 52 ms 31688 KB Output is correct
4 Correct 51 ms 32800 KB Output is correct
5 Correct 104 ms 35152 KB Output is correct
6 Correct 94 ms 35128 KB Output is correct
7 Correct 88 ms 35148 KB Output is correct
8 Correct 96 ms 35116 KB Output is correct
9 Correct 117 ms 35192 KB Output is correct
10 Correct 67 ms 26516 KB Output is correct
11 Correct 165 ms 38560 KB Output is correct
12 Correct 6 ms 11092 KB Output is correct
13 Correct 5 ms 11092 KB Output is correct
14 Correct 6 ms 11092 KB Output is correct
15 Correct 6 ms 11092 KB Output is correct
16 Correct 7 ms 11092 KB Output is correct
17 Correct 5 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 31572 KB Output is correct
21 Correct 22 ms 31572 KB Output is correct
22 Correct 98 ms 35068 KB Output is correct
23 Correct 156 ms 38680 KB Output is correct
24 Correct 152 ms 38604 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12452 KB Output is correct
2 Correct 30 ms 13224 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9708 KB Output is correct
5 Correct 90 ms 20260 KB Output is correct
6 Correct 94 ms 20260 KB Output is correct
7 Correct 5 ms 11092 KB Output is correct
8 Correct 53 ms 16100 KB Output is correct
9 Correct 71 ms 17560 KB Output is correct
10 Correct 28 ms 12448 KB Output is correct
11 Correct 31 ms 13200 KB Output is correct
12 Correct 5 ms 11092 KB Output is correct
13 Correct 5 ms 11208 KB Output is correct
14 Correct 5 ms 11092 KB Output is correct
15 Correct 5 ms 11092 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 28 ms 12852 KB Output is correct
19 Correct 32 ms 13576 KB Output is correct
20 Correct 27 ms 12876 KB Output is correct
21 Correct 31 ms 13216 KB Output is correct
22 Correct 27 ms 12840 KB Output is correct
23 Correct 30 ms 13204 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 22 ms 31552 KB Output is correct
26 Correct 52 ms 31688 KB Output is correct
27 Correct 51 ms 32800 KB Output is correct
28 Correct 104 ms 35152 KB Output is correct
29 Correct 94 ms 35128 KB Output is correct
30 Correct 88 ms 35148 KB Output is correct
31 Correct 96 ms 35116 KB Output is correct
32 Correct 6 ms 11136 KB Output is correct
33 Correct 7 ms 11180 KB Output is correct
34 Correct 7 ms 11208 KB Output is correct
35 Correct 5 ms 11092 KB Output is correct
36 Correct 6 ms 11104 KB Output is correct
37 Correct 6 ms 11092 KB Output is correct
38 Correct 7 ms 11092 KB Output is correct
39 Correct 6 ms 11152 KB Output is correct
40 Correct 37 ms 11988 KB Output is correct
41 Correct 242 ms 13204 KB Output is correct
42 Correct 36 ms 11988 KB Output is correct
43 Correct 250 ms 13164 KB Output is correct
44 Correct 10 ms 11476 KB Output is correct
45 Correct 239 ms 13156 KB Output is correct
46 Correct 255 ms 13148 KB Output is correct
47 Correct 10 ms 11560 KB Output is correct
48 Correct 265 ms 14768 KB Output is correct
49 Correct 258 ms 14720 KB Output is correct
50 Correct 257 ms 14796 KB Output is correct
51 Correct 253 ms 14596 KB Output is correct
52 Correct 253 ms 14736 KB Output is correct
53 Correct 270 ms 16308 KB Output is correct
54 Correct 258 ms 13436 KB Output is correct
55 Correct 245 ms 14248 KB Output is correct
56 Correct 249 ms 13180 KB Output is correct
57 Correct 243 ms 13420 KB Output is correct
58 Correct 8 ms 14932 KB Output is correct
59 Execution timed out 1079 ms 25288 KB Time limit exceeded
60 Halted 0 ms 0 KB -