Submission #763511

#	Time	Username	Problem	Language	Result	Execution time	Memory
763511		raysh07	Catfish Farm (IOI22_fish)	C++17	100 / 100	887 ms	179676 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define INF (long long)(1e18)
 
const int N = 1e5 + 69;
vector <int> ok[N];
map <int, long long> a[N];
unordered_map <int, long long> ac[N];
unordered_map <int, long long> dp[N][2];
vector <int> opt[N];
 
long long val(int i, int j){
    int idx = upper_bound(ok[i].begin(), ok[i].end(), j) - ok[i].begin() - 1;
    assert(idx >= 0);
    return ac[i][ok[i][idx]];
}
 
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for (int i = 0; i < m; i++){
        a[x[i] + 1][y[i] + 1] = w[i];
        ok[x[i] + 1].push_back(y[i] + 1);
    }
    ok[0].push_back(0);
    a[0][0] = 0;
    ok[n + 1].push_back(0);
    a[n + 1][0] = 0;
    ok[n + 2].push_back(0);
    a[n + 2][0] = 0;
    
    for (int i = 0; i < n; i++){
        a[i + 1][0] = 0;
        ok[i + 1].push_back(0);
        sort(ok[i + 1].begin(), ok[i + 1].end());
        
        long long v = 0;
        for (auto &[x, y] : a[i + 1]){
            v += y;
            y = v;
        }
    }
    
    for (int i = 0; i <= n + 2; i++){
        for (auto [x, y] : a[i]){
            ac[i][x] = y;
        }
    }
    
    dp[0][1][0] = dp[0][0][0] = 0; //0, 1 --> not processed / processed 
    opt[0].push_back(0);
    for (int i = 1; i <= n + 1; i++){
        for (int x : ok[i - 1]) opt[i].push_back(x);
        for (int x : ok[i + 1]) opt[i].push_back(x);
        
        sort(opt[i].begin(), opt[i].end());
        opt[i].erase(unique(opt[i].begin(), opt[i].end()), opt[i].end());
        
        for (int j : opt[i]){
            dp[i][0][j] = dp[i][1][j] = -INF;
        }
        if (i != (n + 1)){
        for (int j : opt[i]){
            if (j == 0) continue;
            dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][0] + val(i - 1, j) - val(i, j));
            dp[i][0][j] = max(dp[i][0][j], dp[i - 1][1][0] - val(i, j));
        }
        long long mx = -INF;
        int pt = 1;
        for (int j : opt[i]){
            if (j == 0) continue;
            while (pt != opt[i - 1].size() && opt[i - 1][pt] <= j){
                mx = max(mx, dp[i - 1][0][opt[i - 1][pt]]);
                pt++;
            }
            dp[i][0][j] = max(dp[i][0][j], mx - val(i, j) + val(i - 1, j));
        }
        
        mx = -INF;
        pt = opt[i - 1].size() - 1;
        for (int j : opt[i]){
            if (j == 0) continue;
            while (pt != 0 && opt[i - 1][pt] >= j){
                mx = max(mx, dp[i - 1][1][opt[i - 1][pt]]);
                pt--;
            }
            dp[i][1][j] = max(dp[i][1][j], mx - val(i, j) + val(i + 1, j));
        }
        for (int j : opt[i]){
            if (j == 0) continue;
            dp[i][1][j] = max(dp[i][1][j], dp[i][0][j] + val(i, j) + val(i + 1, j));
        }
        }
        for (int j : opt[i - 1]){
            if (j == 0) continue;
            dp[i][0][0] = max(dp[i][0][0], dp[i - 1][1][j] - val(i, j));
            dp[i][1][0] = max(dp[i][1][0], dp[i - 1][1][j]);
        }
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][0]);
        dp[i][0][0] = max(dp[i][0][0], dp[i - 1][1][0]);
    }
    
    long long sum = 0;
    for (int i = 0; i <= n + 1; i++){
        sum += dp[i][0].size();
        sum += dp[i][1].size();
    }
    
    assert(sum <= 2 * (2 * m + n + 2));
    
    long long ans = -INF;
    ans = max(ans, dp[n + 1][0][0]);
    ans = max(ans, dp[n + 1][1][0]);
    return ans;
}
 
// int main(){
//     int n, m; cin >> n >> m;
    
//     vector <int> a(m), b(m), c(m);
//     for (auto &x : a) cin >> x;
//     for (auto &x : b) cin >> x;
//     for (auto &x : c) cin >> x;
    
//     cout << max_weights(n, m, a, b, c) << "\n";
//     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:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while (pt != opt[i - 1].size() && opt[i - 1][pt] <= j){
      |                    ~~~^~~~~~~~~~~~~~~~~~~~

• 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