Submission #831138

#	Time	Username	Problem	Language	Result	Execution time	Memory
831138		Wael	Radio Towers (IOI22_towers)	C++17	Compilation error	0 ms	0 KiB

towers

#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int const Mx = 1e5 + 10;
long long n , m;
map<int , int>cost[Mx] , vis[Mx];
vector<int>possible[Mx];
vector<long long>pref[Mx] , dp[3][Mx];

long long max_weights(int N, int M , vector<int> X, vector<int> Y, vector<int> W) {
    m = M , n = N;
    long long ans = 0 , Sum = 0;
    int MaxX = 0 , Even = 1;

    for(int i = 0 ; i < m ; ++i) {
        ++X[i];
        ++Y[i];
        Sum += W[i];
        if(X[i] % 2 == 0) Even = 0;
        MaxX = max(MaxX , X[i]);
        if(vis[X[i] - 1][Y[i]] == 0) possible[X[i] - 1].push_back(Y[i]);
        if(vis[X[i] + 1][Y[i]] == 0) possible[X[i] + 1].push_back(Y[i]);
        if(vis[X[i]][Y[i]] == 0) possible[X[i]].push_back(Y[i]);
        vis[X[i] - 1][Y[i]] = 1;
        vis[X[i] + 1][Y[i]] = 1;
        vis[X[i]][Y[i]] = 1;
        cost[X[i]][Y[i]] = W[i];
    }

    if(Even) return Sum;
    for(int i = 1 ; i <= n ; ++i) {
        possible[i].push_back(0);
        sort(possible[i].begin() , possible[i].end());
        for(auto j : possible[i]) {
            long long cur = 0;
            if(pref[i].size()) cur = pref[i].back();
            cur += cost[i][j];
            pref[i].push_back(cur);
            dp[0][i].push_back(0);
            dp[1][i].push_back(0);
        }
    }

    if(MaxX <= 2) {
        if(n == 2) return max(pref[1].back() , pref[2].back());
        long long sum = pref[2].back();
        int Req = 0;
        for(int j = 0 ; j < possible[1].size() ; ++j) {
            while(Req + 1 < possible[2].size() && possible[2][Req + 1] <= possible[1][j]) ++Req;
            ans = max(ans , sum - pref[2][Req] + pref[1][j]);
        }
        return ans;
    }

    for(int i = 2 ; i <= n ; ++i) {
        for(int J = 0 ; J < possible[i].size() ; ++J) {
            int j = possible[i][J];
            int Req1 = 0 , Req2 = 0;
            while(Req1 + 1 < possible[i - 1].size() && possible[i - 1][Req1 + 1] <= j) ++Req1;
            for(int K = 0 ; K <  possible[i - 1].size() ; ++K) {
                int k = possible[i - 1][K];
                while(Req2 + 1 < possible[i].size() && possible[i][Req2 + 1] <= k) ++Req2;
                if(k <= j) dp[0][i][J] = max(dp[0][i][J] , dp[0][i - 1][K] + pref[i - 1][Req1] - pref[i - 1][K]);
                else dp[1][i][J] = max(dp[1][i][J] , max(dp[0][i - 1][K] , dp[1][i - 1][K]) + pref[i][Req2] - pref[i][J]);
            }
            if(i >= 3) {
                int Req = 0;
                for(int K = 0 ; K < possible[i - 2].size() ; ++K) {
                    int k = possible[i - 2][K];
                    while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= max(j , k)) ++Req;
                    dp[0][i][J] = max(dp[0][i][J] , max(dp[0][i - 2][K] , dp[1][i - 2][K]) + pref[i - 1][Req]);
                }
            }
            ans = max(ans , dp[0][i][J]);
            ans = max(ans , dp[1][i][J]);
        }
    }

    return ans;
}
/*
3 4
1 1 5
1 2 10
2 1 5
3 1 5
*/

Compilation message (stderr)

towers.cpp:3:10: fatal error: fish.h: No such file or directory
    3 | #include "fish.h"
      |          ^~~~~~~~
compilation terminated.