Submission #795479

#TimeUsernameProblemLanguageResultExecution timeMemory
795479ln_eCatfish Farm (IOI22_fish)C++17
32 / 100
180 ms100480 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho #include "fish.h" using ll=long long; using ld=long double; int const INF=1000000005; ll const LINF=1000000000000000005; ll const mod=1000000007; ld const PI=3.14159265359; ll const MAX_N=3e5+5; ld const EPS=0.00000001; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define f first #define s second #define pb push_back #define mp make_pair #define endl '\n' #define sz(a) (int)a.size() #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; long long a[100005][10],dp[100005][10][10],sum[100005][10]; bool check1(vector<int>x){ for(ll i=0;i<x.size();i++) { if(x[i]%2==1){ return 0; } } return 1; } bool check2(vector<int>x){ for(ll i=0;i<x.size();i++) { if(x[i]>1){ return 0; } } return 1; } bool check3(vector<int>y){ for(ll i=0;i<y.size();i++){ if(y[i]!=0){ return 0; } } return 1; } long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { if(check1(X)){ ll ans=0; for(ll i=0;i<M;i++) { ans+=W[i]; } return ans; }else if(check2(X)){ ll sum1=0,sum2=0,ans=0; for(ll i=0;i<M;i++) { if(X[i]==0){ sum1+=W[i]; }else sum2+=W[i]; } ans=max(sum1,sum2); if(N>2){ int x[3][100005]; for(int i=0;i<=1;i++) { for(ll j=0;j<N;j++) { x[i][j]=0; } } for(int i=0;i<M;i++) { x[X[i]][Y[i]]=W[i]; } ll sum2[100005]; memset(sum2,0,sizeof(sum2)); for(ll i=0;i<N;i++) { if(i-1>=0){ sum2[i]=sum2[i-1]; } sum2[i]+=x[0][i]; } ll idk=0; for(ll i=N-1;i>=1;i--) { idk+=x[1][i]; ans=max(ans,idk+sum2[i-1]); } } return ans; }else if(check3(Y)){ for(ll i=0;i<M;i++) { a[X[i]+1][Y[i]+1]=W[i]; } for(ll j=0;j<=8;j++) { for(ll k=0;k<=8;k++) { dp[0][j][k]=-LINF; } } dp[0][0][0]=0; for(ll i=1;i<=N;i++) { for(ll j=1;j<=8;j++) { sum[i][j]=sum[i][j-1]; sum[i][j]+=a[i][j]; } } ll ans=0; for(ll i=1;i<=N;i++) { for(ll j=0;j<=8;j++) //j-ul meu { for(ll k=0;k<=8;k++) //j-ul precedent { for(ll mx=0;mx<=8;mx++){ //mx acoperit precedent ll val=dp[i-1][k][mx]; if(k>j){ val+=sum[i][k]; val-=sum[i][j]; } if(j>mx){ val+=sum[i-1][j]; val-=sum[i-1][mx]; } dp[i][j][max(k,j)]=max(dp[i][j][max(k,j)],val); ans=max(ans,dp[i][j][max(k,j)]); } } } } return ans; } }

Compilation message (stderr)

fish.cpp: In function 'bool check1(std::vector<int>)':
fish.cpp:23:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(ll i=0;i<x.size();i++)
      |                    ~^~~~~~~~~
fish.cpp: In function 'bool check2(std::vector<int>)':
fish.cpp:32:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(ll i=0;i<x.size();i++)
      |                ~^~~~~~~~~
fish.cpp: In function 'bool check3(std::vector<int>)':
fish.cpp:41:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 | for(ll i=0;i<y.size();i++){
      |            ~^~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:142:1: warning: control reaches end of non-void function [-Wreturn-type]
  142 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...