Submission #836935

#TimeUsernameProblemLanguageResultExecution timeMemory
836935MeGustaElArroz23Catfish Farm (IOI22_fish)C++17
0 / 100
1120 ms2097152 KiB
#include "fish.h" #include <vector> #include<bits/stdc++.h> using namespace std; long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w) { #define ll long long #define vi vector<long long> #define vvi vector<vi> #define vvvi vector<vvi> #define vb vector<bool> #define pii pair<long long,long long> #define vii vector<pii> #define vvii vector<vii> #define pb push_back #define fi first #define se second vvi posh(n); for (int i=0;i<m;i++) posh[x[i]].pb(y[i]-1); for (int i=0;i<n;i++) posh[i].pb(n-1); for (int i=0;i<n;i++) sort(posh[i].begin(),posh[i].end()); vvii cats(n); for (int i=0;i<m;i++) cats[x[i]].pb(pii{y[i],w[i]}); //for (int i=0;i<n;i++) cats[i].pb(pii{n,0}); for (int i=0;i<n;i++) sort(cats[i].begin(),cats[i].end()); //cerr << "HHHHHHHHHHHHHH\n"; vvi pref(n,vi(n+1,0)); for (int i=0;i<n;i++){ int k=0; for (int j=1;j<=n;j++){ if (k<cats[i].size() && cats[i][k].fi==j-1){ pref[i][j]=pref[i][j-1]+cats[i][k].se; k++; } else pref[i][j]=pref[i][j-1]; } } //cerr << "HHHHHHHHHHHHHH\n"; vvvi dp(n); //columna, h[i], h[i-1] //hago dp[1] dp[1]=vvi(posh[1].size(),vi(posh[0].size(),0)); for (int i=0;i<posh[1].size();i++){ for (int j=0;j<posh[0].size();j++){ if (posh[1][i]>posh[0][j]) dp[1][i][j]=pref[0][posh[1][i]+1]-pref[0][posh[0][j]+1]; else dp[1][i][j]=pref[1][posh[0][j]+1]-pref[1][posh[1][i]+1]; //cerr << "1: "<< i << ' ' << j << ' ' << dp[1][i][j] << '\n'; } } // //cerr << "HHHHHHHHHHHHHH\n"; for (int i=2;i<n;i++){ dp[i]=vvi(posh[i].size(),vi(posh[i-1].size(),0)); for (int j=0;j<posh[i].size();j++){ //altura for (int k=0;k<posh[i-1].size();k++){ //altura ant for (int l=0;l<posh[i-2].size();l++){ ll ans=dp[i-1][k][l]; if (posh[i][j]>posh[i-1][k]){ if (posh[i][j]>posh[i-2][l]) ans+=pref[i-1][posh[i][j]+1]-pref[i-1][ max(posh[i-2][l],posh[i-1][k]) +1]; } else ans+=pref[i][posh[i-1][k]+1]-pref[i][posh[i][j]+1]; dp[i][j][k]=max(dp[i][j][k],ans); //cerr << i << ": " << posh[i][j] << ' ' << posh[i-1][k] << ' ' << dp[i][j][k] << '\n'; } } } } //cerr << "HHHHHHHHHHHHHH\n"; int res=0; for (vi v:dp[n-1]){ for (int b:v) res=max(res,b); } return res; }

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    if (k<cats[i].size() && cats[i][k].fi==j-1){
      |        ~^~~~~~~~~~~~~~~
fish.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=0;i<posh[1].size();i++){
      |               ~^~~~~~~~~~~~~~~
fish.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int j=0;j<posh[0].size();j++){
      |                ~^~~~~~~~~~~~~~~
fish.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int j=0;j<posh[i].size();j++){ //altura
      |                ~^~~~~~~~~~~~~~~
fish.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int k=0;k<posh[i-1].size();k++){ //altura ant
      |                 ~^~~~~~~~~~~~~~~~~
fish.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int l=0;l<posh[i-2].size();l++){
      |                  ~^~~~~~~~~~~~~~~~~
#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...