Submission #838241

#	Time	Username	Problem	Language	Result	Execution time	Memory
838241		Theo830	Catfish Farm (IOI22_fish)	C++17	64 / 100	1089 ms	143892 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
#define ii pair<int,long long>
#define F first
#define S second
#define iii pair<ii,int>
using namespace std;
long long dp[3000005][3];
vector<iii>pre[100005];
int n;
long long sum(int i,int j){
    if(i >= n){
        return 0;
    }
    int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
    posi--;
    return pre[i][posi].F.S;
}
long long solve(int i,int j,int k){
    int pos = -1;
    long long sumi = 0;
    if(i >= n){
        return 0;
    }
    if(j < 0 || j > n){
        return 0;
    }
    if(k == 0 || k == 2){
        int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j,0),0)) - pre[i].begin();
        j = pre[i][posi].F.F;
        pos = pre[i][posi].S;
    }
    else{
        int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
        posi--;
        j = pre[i][posi].F.F;
        pos = pre[i][posi].S;
    }
    if(dp[pos][k] != -1){
        return dp[pos][k];
    }
    sumi = sum(i,j);
    long long ans = 0;
    if(k == 0 || k == 2){
        ans = max(ans,solve(i,j+1,k));
        long long val = 0;
        if(k == 0){
            val = sum(i-1,j);
        }
        long long sum2 = sum(i+1,j);
        ans = max(ans,solve(i+1,j,0) - sumi + val);
        ans = max(ans,solve(i+1,j,1) + val + sum2);
        ans = max(ans,solve(i+2,0,2) + val + sum2);
        ans = max(ans,solve(i+2,0,0) + val);
    }
    else{
        long long sum2 = sum(i+1,j);
        ans = max(ans,solve(i,j-1,1));
        ans = max(ans,solve(i+2,0,0) - sumi);
        ans = max(ans,solve(i+2,0,2) - sumi + sum2);
        ans = max(ans,solve(i+1,j,1) - sumi + sum2);
    }
    return dp[pos][k] = ans;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N;
    memset(dp,-1,sizeof dp);
    long long sum = 0;
    for(int i = 0;i < M;i++){
        Y[i]++;
        pre[X[i]].push_back(iii(ii(Y[i],W[i]),0));
        pre[X[i]].push_back(iii(ii(Y[i] - 1,0),0));
        if(X[i] > 0){
            pre[X[i] - 1].push_back(iii(ii(Y[i],0),0));
        }
        if(X[i] < n-1){
            pre[X[i] + 1].push_back(iii(ii(Y[i],0),0));
        }
    }
    int cur = 0;
    for(int i = 0;i < N;i++){
        pre[i].push_back(iii(ii(0,0),0));
        pre[i].push_back(iii(ii(n,0),0));
        sort(pre[i].begin(),pre[i].end());
        int m = pre[i].size();
        pre[i][0].S = cur;
        cur++;
        for(int j = 1;j < m;j++){
            pre[i][j].F.S += pre[i][j-1].F.S;
            pre[i][j].S = cur;
            cur++;
        }
    }
    return solve(0,0,2);
}
/*
int main() {
  srand(time(0));
  int N = 2, M = 1;
  //assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    W[i] = 1000000000;
    X[i] = 0;
    Y[i] = 0;
    //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;
}
*/

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:68:15: warning: unused variable 'sum' [-Wunused-variable]
   68 |     long long sum = 0;
      |               ^~~

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