Submission #1056163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056163		mychecksedad	Catfish Farm (IOI22_fish)	C++17	0 / 100	45 ms	66756 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], mxpref[N], mxpref2[N];
vector<pair<ll, ll>> a[N];
vector<ll> b[N];
ll mx[N];
int n;
ll get(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : pref[pos][x]);
}
ll getmxpref2(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : mxpref2[pos][x]);
}
ll getmxpref(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : mxpref[pos][x]);
}
ll getsuf(int pos, ll idx){
  if(pos >= n) return 0;
  int x = lower_bound(all(b[pos]), idx) - b[pos].begin();
  return (x == b[pos].size() ? 0 : suf[pos][x]);
}
ll getdp(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : dp[pos][x]);
}
ll getdp2(int pos, ll idx){
  if(pos >= n) return 0;
  int x = upper_bound(all(b[pos]), idx) - b[pos].begin(); --x;
  return (x == -1 ? 0 : dp2[pos][x]);
}
long long max_weights(int nn, int m, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
  n = nn;
  for(int i = 0; i < m; ++i){
    a[X[i]].pb({Y[i] + 1, W[i]});
    // a[X[i]][Y[i] + 1] = W[i];
    b[X[i]].pb(Y[i]);
  }
  for(int i = 0; i < n; ++i){
    a[i].pb({n + 1, 0});
    b[i].pb(n);
    sort(all(a[i]));
  }
  for(int i = 0; i < n; ++i){
    pref[i].resize(b[i].size() + 1);
    suf[i].resize(b[i].size() + 1);
    dp[i].resize(b[i].size() + 1);
    dp2[i].resize(b[i].size() + 1);
    mxpref[i].resize(b[i].size() + 1);
    mxpref2[i].resize(b[i].size() + 1);
    pref[i][0] = 0;
    for(int j = 1; j < b[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
  }
// for(int i = 0; i < n; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << pref[i][j] << ' ';
// en;
// }
// en;en;
// for(int i = 0; i < n; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << b[i][j] << ' ';
// en;
// }
// en;en;

  for(int i = 0; i < b[0].size(); ++i){
    dp[0][i] = dp2[0][i] = get(1, b[0][i]);
  }
  mx[0] = pref[1].back();
  suf[0][b[0].size()] = 0;
  for(int j = b[0].size() - 1; j >= 0 ;--j) suf[0][j] = max(suf[0][j + 1], dp[0][j]);
   
  return 0ll;

  int i = 0;
  mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
  mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);

  for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
  for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));

  for(i = 1; i < n; ++i){
    mx[i] = 0;
    ll mx_pref = 0, mx_pref2 = 0;
    for(int j = 0; j < b[i].size(); ++j){
      ll pos = b[i][j];
      ll A = get(i - 1, pos);
      ll B = get(i, pos);
      ll C = get(i + 1, pos);
      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 = add - B - A; //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, getmxpref2(i - 1, pos));//max(mx_pref2, getdp2(i - 1, pos) - 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, pos) + x);//suf[i - 1][j] + x);
      if(i > 1){
        mx_pref = max(mx_pref, getmxpref(i - 2, pos));//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, pos) - 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, pos) - A);//suf[i - 2][j] - pref[i - 1][j]);
      }
      
      // cout << dp[i][j] << ' ' << i << ' ' << pos << endl; 
      mx[i] = max(mx[i], dp[i][j]);
    }
    suf[i][b[i].size()] = 0;

    for(int j = int(b[i].size()) - 1; j >= 0 ;--j) suf[i][j] = max(suf[i][j + 1], dp[i][j]);

    mxpref[i][0] = dp[i][0] - get(i + 1, b[i][0]);
    mxpref2[i][0] = dp2[i][0] - get(i + 1, b[i][0]) - get(i, b[i][0]);

    for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
    for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
    // for(int j = n-1; j >= 0 ;--j) suf2[i][j] = max(suf2[i][j + 1], dp[i][j]);
    // en;
  }
// for(int i = 0; i < n; ++i){
//   for(int j = 0; j < b[i].size(); ++j) cout << 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:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   return (x == b[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:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int j = 1; j < b[0].size(); ++j) pref[i][j] = pref[i][j - 1] + a[i][j - 1].ss;
      |                    ~~^~~~~~~~~~~~~
fish.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int i = 0; i < b[0].size(); ++i){
      |                  ~~^~~~~~~~~~~~~
fish.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
      |                  ~~^~~~~~~~~~~~~
fish.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][j]));
      |                  ~~^~~~~~~~~~~~~
fish.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int j = 0; j < b[i].size(); ++j){
      |                    ~~^~~~~~~~~~~~~
fish.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int j = 1; j < b[i].size() ;++j) mxpref[i][j] = max(mxpref[i][j  - 1], dp[i][j] - get(i + 1, b[i][j]));
      |                    ~~^~~~~~~~~~~~~
fish.cpp:140:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int j = 1; j < b[i].size() ;++j) mxpref2[i][j] = max(mxpref2[i][j  - 1], dp2[i][j] - get(i + 1, b[i][j]) - get(i, b[i][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