Submission #1056017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056017		mychecksedad	Catfish Farm (IOI22_fish)	C++17	0 / 100	36 ms	41664 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int> 
#define ff first
#define ss second
const int N = 100005;

// ll dp[N][N], pref[N][N], mx[N], dp2[N][N], suf[N][N];
vector<ll> dp2[N], dp[N], pref[N], suf[N];
vector<pair<ll, ll>> a[N];
ll mx[N];
ll get(int pos, ll idx){
  int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
  return (x == -1 ? 0 : pref[pos][x]);
}
ll getsuf(int pos, ll idx){
  int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin();
  return (x == a[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
  int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
  return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
  int x = upper_bound(all(a[pos]), pair<ll,ll>{idx, LONG_LONG_MAX}) - a[pos].begin(); --x;
  return (x == -1 ? 0 : dp2[pos][x]);
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  for(int i = 0; i < m; ++i){
    a[X[i]].pb({Y[i] + 1, W[i]});
    // a[X[i]][Y[i] + 1] = W[i];
  }
  for(int i = 0; i < n; ++i){
    if(a[i].empty()) a[i].pb({n, 0});
    else if(a[i].back().ff != n) a[i].pb({n, 0});
    sort(all(a[i]));
  }
  for(int i = 0; i < n; ++i){
    pref[i].resize(a[i].size() + 1);
    suf[i].resize(a[i].size() + 1);
    dp[i].resize(a[i].size() + 1);
    dp2[i].resize(a[i].size() + 1);
    pref[i][0] = a[i][0].ss;
    for(int j = 1; j < a[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j].ss;
  }
  for(int i = 0; i < a[0].size(); ++i){
    dp[0][i] = dp2[0][i] = get(1, a[0][i].ff);
  }
  mx[0] = pref[1].back();
  suf[0][a[0].size()] = 0;
  for(int j = a[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
   
  for(int i = 1; i < n; ++i){
    mx[i] = 0;
    ll mx_pref = 0, mx_pref2 = 0;
    for(int j = 0; j < a[i].size(); ++j){
      ll A = get(i - 1, a[i][j].ff);
      ll B = get(i, a[i][j].ff);
      ll C = get(i + 1, a[i][j].ff);
      ll add = A + C; //pref[i + 1][j] +  pref[i - 1][j];
      dp[i][j] = add;
      if(i > 2) dp[i][j] = max(dp[i][j], mx[i - 3] + add);
      dp2[i][j] = dp[i][j];

      // cout << i << ' ' << j << ' ' << add1 << ' ' <<add2 << ' ';
      ll x = C - B; //add - pref[i - 1][j] - pref[i][j];
      // for(int j2 = j + 1; j2 <= n; ++j2){
      //   dp[i][j] = max(dp[i][j], dp[i - 1][j2] + x);
      // }
      mx_pref2 = max(mx_pref2, getdp2(i - 1, j) - A - B); //dp2[i - 1][j] - pref[i - 1][j] - pref[i][j]);
      dp[i][j] = max(dp[i][j], mx_pref2 + add);
      dp2[i][j] = max(dp2[i][j], mx_pref2 + add);
      dp[i][j] = max(dp[i][j], getsuf(i - 1, j) + x);//suf[i - 1][j] + x);
      if(i > 1){
        mx_pref = max(mx_pref, getdp(i - 2, j) - A);//dp[i - 2][j] - pref[i - 1][j]);
        dp[i][j] = max(dp[i][j], mx_pref + add);
        dp[i][j] = max(dp[i][j], getsuf(i - 2, j) - A);//suf[i - 2][j] - pref[i - 1][j]);
        dp2[i][j] = max(dp2[i][j], mx_pref + add);
        dp2[i][j] = max(dp2[i][j], getsuf(i - 2, j) - A);//suf[i - 2][j] - pref[i - 1][j]);
      }
      

      // cout << dp[i][j] << '\n'; 
      mx[i] = max(mx[i], dp[i][j]);
    }
    suf[i][a[i].size()] = 0;

    for(int j = int(a[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);
    // for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
    // en;
  }
  ll ans = mx[n - 1];

  return ans;
}

Compilation message (stderr)

fish.cpp: In function 'long long int getsuf(int, long long int)':
fish.cpp:24:13: 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]
   24 |   return (x == a[pos].size() ? 0 : suf[pos][x]);
      |           ~~^~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:50:22: 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]
   50 |     for(int j = 1; j < a[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j].ss;
      |                    ~~^~~~~~~~~~~~~
fish.cpp:52:20: 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]
   52 |   for(int i = 0; i < a[0].size(); ++i){
      |                  ~~^~~~~~~~~~~~~
fish.cpp:62:22: 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]
   62 |     for(int j = 0; j < a[i].size(); ++j){
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16