Submission #1161649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161649		KK_1729	Catfish Farm (IOI22_fish)	C++20	0 / 100	1095 ms	12388 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<long long> a){

    for (auto x: a) cout << x << " ";
    cout << endl;
}
long long max(long long x, long long y){
  if (x > y) return x;
  else return y;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {


    vector<vector<pair<int, int>>> o(N+1);
    FOR(i,0,M){
        o[X[i]].pb({Y[i], W[i]});
    }
    FOR(i,0,N) sort(all(o[i]));
    FOR(i,0,N){
      int t = o[i].size();
        if (t > 0){
            if (o[i][0].first != 0){
                o[i].pb({0,0});
            }
            if (o[i][t-1].first != N-1){
                o[i].pb({N-1, 0});
            }
        }
    }
    vector<long long> prefix1(N+1);
    vector<long long> dp1(N+1);
    vector<long long> prefix2(N+1);
    vector<long long> dp2(N+1);
    
    for (auto x: o[0]) prefix1[x.first] += x.second;
    FOR(i,1,N) prefix1[i] += prefix1[i-1];
    long long answer = 0;
//     printVector(prefix1);
    FOR(i,1,N){

        for (auto x: o[i]) prefix2[x.first] += x.second;
        FOR(j,1,N) prefix2[i] += prefix2[i-1];
        vector<pair<int, int>> e;
        for (auto x: o[i-1]) e.pb({x.first, 0});
        for (auto x: o[i]) e.pb({x.first, -1});
        sort(all(e));
        int c = 0ll;
        for (auto item: e){
//             if (item.second == 0){
                c = max(c, dp1[item.first]-prefix1[item.first]);
//             }else{
                dp2[item.first] = max(dp2[item.first], prefix1[item.first]+c);
//             }
        }

        int d = 0ll;
        reverse(all(e));
        for (auto item: e){
//             if (item.second == 0){
                d = max(d, dp1[item.first]+prefix2[item.first]);  
//             }else{
                dp2[item.first] = max(dp2[item.first], -prefix2[item.first]+d);
//             }   
        }
        FOR(i,1,N) answer = max(answer, dp2[i]);
//         printVector(dp2);
        swap(prefix1, prefix2);
        swap(dp1, dp2);
        dp2.clear();
        prefix2.clear();
        dp2.resize(N);
        prefix2.resize(N);
    }

    return answer;
}

• 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