Submission #1216838

#TimeUsernameProblemLanguageResultExecution timeMemory
1216838cpdreamerCatfish Farm (IOI22_fish)C++17
35 / 100
1105 ms2162688 KiB
#include "fish.h" #include <bits/stdc++.h> using namespace std; const long long INF = 1e17; typedef long long ll; const ll MOD = (ll)1e9+7; #define P pair #define S second #define F first #define pb push_back #define V vector #define all(v) v.begin(), v.end() long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) { V<V<ll>>pref(N,V<ll>(N+1)); for (int i=0;i<M;i++) { pref[X[i]][Y[i]+1]+=W[i]; } for (int i=0;i<N;i++) { for (int j=1;j<=N;j++) { pref[i][j]+=pref[i][j-1]; } } ll dp[(int)N][N+1][2]; memset(dp,0,sizeof(dp)); for (int i=1;i<N;i++) { for (int j=0;j<=N;j++) { for (int g=0;g<=N;g++) { dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][g][0],dp[i-1][g][1])+max(pref[i][g]-pref[i][j],0LL)); dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][g][0],dp[i-1][g][1]+max(pref[i-1][j]-pref[i-1][g],0LL))); } } } ll ans=0; for (int i=0;i<=N;i++) { ans=max(ans,max(dp[N-1][i][0],dp[N-1][i][1])); } return ans; }
#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...