Submission #841216

#	Time	Username	Problem	Language	Result	Execution time	Memory
841216		Cookie	Catfish Farm (IOI22_fish)	C++17	100 / 100	914 ms	186272 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
#include<fstream>

using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 1e5 + 5;
int n, m;
ll x[3 * mxn + 1], y[3 * mxn + 1], w[3 * mxn + 1];
vt<ll> take[mxn + 1], notake[mxn + 1], pref[mxn + 1];
ll mxval[mxn + 1];
vt<ll> prefmx[mxn + 1], sufmx[mxn + 1], prefmx2[mxn + 1], sufmx2[mxn + 1];
vt<ll>comp[mxn + 1];

void ckmax(ll &a, ll b){
    a = max(a, b);
}
int getr(int id, int x){
    return(lower_bound(comp[id].begin(), comp[id].end(), x) - comp[id].begin() + 1);
}
int getl(int id, int x){
    return(upper_bound(comp[id].begin(), comp[id].end(), x) - comp[id].begin());
}
ll solve(){
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        
        for(int j = 1; j <= sz(comp[i]); j++){
            
            
            if(i > 1){
                
                notake[i][j] = take[i][j] = pref[i - 1][getl(i - 1, comp[i][j - 1])];
                ckmax(take[i][j], sufmx[i - 1][getr(i - 1, comp[i][j - 1])] - pref[i][j]);
                ckmax(take[i][j], prefmx[i - 1][getl(i - 1, comp[i][j - 1])]);
                ckmax(take[i][j], prefmx2[i - 1][getl(i - 1, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
                ckmax(notake[i][j], prefmx[i - 1][sz(comp[i - 1])]);
                ckmax(notake[i][j], prefmx2[i - 1][getl(i - 1, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
            }
            
            if(i > 2){
               
                ckmax(take[i][j], prefmx[i - 2][getl(i - 2, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
                ckmax(take[i][j], sufmx[i - 2][getr(i - 2, comp[i][j - 1])]);
            }if(i > 3){
               
                
                ckmax(take[i][j], mxval[i - 3] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
                ckmax(notake[i][j], mxval[i - 3] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);

            }
            ll tmp = take[i][j];
            if(i < n){
                tmp += pref[i + 1][getl(i + 1, comp[i][j - 1])];
            }
            ckmax(ans, tmp);
            if(i < n)ckmax(mxval[i], take[i][j] + pref[i + 1][getl(i + 1, comp[i][j - 1])]);
            //cout << i << " " << comp[i][j - 1] << " " << take[i][j] << "\n";
        }
        
        for(int j = 1; j <= sz(comp[i]); j++){
            prefmx[i][j] = max(prefmx[i][j - 1], take[i][j]);
            prefmx2[i][j] = max(prefmx2[i][j - 1], notake[i][j] - pref[i][j]);
        }
        for(int j = sz(comp[i]); j >= 1; j--){
            if(i < n)sufmx[i][j] = max(sufmx[i][j + 1], take[i][j] + pref[i + 1][getl(i + 1, comp[i][j - 1])]);
           
        }
        
       // sp3[i].init();
       
    }
    return(ans);
}
map<int, ll>cost[mxn + 1];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
    n = N; m = M;
    ll ans  =0;
    for(int i = 1; i <= m; i++){
        x[i] = ++X[i - 1]; y[i] = ++Y[i - 1]; w[i] = W[i - 1];
        cost[x[i]][y[i]] += w[i];
        for(int j = max(x[i] - 1, (ll)1); j <= min(x[i] + 1, (ll)n); j++){
            comp[j].pb(y[i]);
        }
    }
    
    for(int i = 1; i <= n; i++){
        comp[i].pb(1);
        sort(comp[i].begin(), comp[i].end());
        comp[i].resize(unique(comp[i].begin(), comp[i].end()) - comp[i].begin());
        int need = sz(comp[i]) + 3;
        take[i].resize(need); notake[i].resize(need); pref[i].resize(need); prefmx[i].resize(need); prefmx2[i].resize(need); sufmx[i].resize(need);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= sz(comp[i]); j++){
            pref[i][j] = pref[i][j - 1] + cost[i][comp[i][j - 1]];
            
        }
    }
    
    return(solve());
}
/*
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}

*/
//741526820812

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:91:8: warning: unused variable 'ans' [-Wunused-variable]
   91 |     ll ans  =0;
      |        ^~~

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