Submission #1037276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037276		Issa	Catfish Farm (IOI22_fish)	C++17	0 / 100	92 ms	35112 KiB

fish

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int maxn = 3e3 + 100;
const int maxl = 11;

int n;
vector<ll> dp[maxn][2];
vector<int> d[maxn];
vector<pll> a[maxn];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N;
    for(int i = 0; i < M; i++){
        X[i]++; Y[i]++;
        a[X[i]].push_back({Y[i], W[i]});
    }
    for(int i = 1; i <= n; i++){
        for(auto [j, x]: a[i]){
            d[i].push_back(j);
            d[i].push_back(j-1);
        }
        for(auto [j, x]: a[i-1]) d[i].push_back(j);
        for(auto [j, x]: a[i+1]) d[i].push_back(j);
        sort(d[i].begin(), d[i].end());
        d[i].resize(unique(d[i].begin(), d[i].end()) - d[i].begin());
        dp[i][0] = dp[i][1] = vector<ll>(d[i].size(), -1e18 * (i > 1));
        sort(a[i].begin(), a[i].end());
    }
    for(int i = 1; i < n; i++){
        vector<tuple<int, int, int>> v;
        for(auto [j, x]: a[i]) v.push_back({j, 0, x});
        for(auto [j, x]: a[i+1]) v.push_back({j, 1, x});
        for(int j = 0; j < d[i].size(); j++){
            v.push_back({d[i][j], 2, j});
        }
        for(int j = 0; j < d[i+1].size(); j++){
            v.push_back({d[i+1][j], 3, j});
        }
        sort(v.begin(), v.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
            auto [a0, a1, a2] = a; auto [b0, b1, b2] = b;
            if(a0 != b0) return a0 > b0;
            return a1 < b1;
        });
        ll mx = -1e18;
        for(auto [x, c, j]: v){
            if(c == 1) mx += j;
            else if(c == 2) mx = max({mx, dp[i][0][j], dp[i][1][j]});
            else if(c == 3) dp[i+1][0][j] = max(dp[i+1][0][j], mx);
        }
        sort(v.begin(), v.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
            auto [a0, a1, a2] = a; auto [b0, b1, b2] = b;
            if(a0 != b0) return a0 < b0;
            return a1 < b1;
        });
        mx = -1e18;
        for(auto [x, c, j]: v){
            if(c == 0) mx += j;
            else if(c == 2) mx = max(mx, dp[i][1][j]);
            else if(c == 3) dp[i+1][1][j] = max(dp[i+1][1][j], mx);
        }
        ll sum = 0, mx1 = -1e18; mx = -1e18;
        for(int j = 0, k = 0; j < d[i-1].size(); j++){
            while(k < a[i].size() && a[i][k].first <= d[i-1][j]){
                sum += a[i][k++].second;
            }
            mx1 = max(mx1, max(dp[i-1][0][j], dp[i-1][1][j]) + sum);
            mx = max(mx, max(dp[i-1][0][j], dp[i-1][1][j]));
        }
        for(int j = 0, k = 0; j < d[i+1].size(); j++){
            while(k < a[i].size() && a[i][k].first <= d[i+1][j]){
                mx += a[i][k++].second;
            }
            dp[i+1][0][j] = max({dp[i+1][0][j], mx, mx1});
            dp[i+1][1][j] = max({dp[i+1][1][j], mx, mx1});
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, *max_element(dp[i][0].begin(), dp[i][0].end()));
        ans = max(ans, *max_element(dp[i][1].begin(), dp[i][1].end()));
    }
    return ans;
} 
// for(int i = 1; i < n; i++){
//     for(int j = 0; j <= n; j++){
//         for(int k = 0; k <= n; k++){
//             if(k >= j) dp[i+1][k][1] = max(dp[i+1][k][1], dp[i][j][1] + a[i][k] - a[i][j]);
//             if(k <= j) dp[i+1][k][0] = max(dp[i+1][k][0], max(dp[i][j][1], dp[i][j][0]) + a[i+1][j] - a[i+1][k]);                  
//             if(i > 1){
//                 dp[i+1][k][0] = max(dp[i+1][k][0], max(dp[i-1][j][1], dp[i-1][j][0]) + a[i][max(j, k)]);
//                 dp[i+1][k][1] = max(dp[i+1][k][1], max(dp[i-1][j][1], dp[i-1][j][0]) + a[i][max(j, k)]);
//             }
//         }
//     }
// }

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:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = 0; j < d[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
fish.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0; j < d[i+1].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:65:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int j = 0, k = 0; j < d[i-1].size(); j++){
      |                               ~~^~~~~~~~~~~~~~~
fish.cpp:66:21: 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]
   66 |             while(k < a[i].size() && a[i][k].first <= d[i-1][j]){
      |                   ~~^~~~~~~~~~~~~
fish.cpp:72:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j = 0, k = 0; j < d[i+1].size(); j++){
      |                               ~~^~~~~~~~~~~~~~~
fish.cpp:73:21: 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]
   73 |             while(k < a[i].size() && a[i][k].first <= d[i+1][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