Submission #1004717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004717		andrei_iorgulescu	Catfish Farm (IOI22_fish)	C++17	3 / 100	273 ms	96168 KiB

fish

#include <bits/stdc++.h>
#include "fish.h"

using namespace std;

using integer = int;

#define int long long

int n,m;
vector<pair<int,int>> a[100005];
vector<int> sp[100005];
vector<int> poz[100005];
vector<int> dp0[100005],dp1[100005];
vector<int> mp_dp0[100005],mp_dp1[100005],ms_dp0[100005],ms_dp1[100005];
vector<int> lol1[100005];///maxime pe prefix din dp1[i][h] - f(i,h)
vector<int> lol2[100005];///maxime pe sufix din max(dp0[i][h],dp1[i][h]) + f(i + 1,h)

int max_idx(int col,int h)
{
    int st = -1,pas = 1 << 16;
    while (pas != 0)
    {
        if (st + pas < poz[col].size() and poz[col][st + pas] <= h)
            st += pas;
        pas /= 2;
    }
    return st;
}

int max_idx_2(int col,int h)
{
    int st = -1,pas = 1 << 16;
    while (pas != 0)
    {
        if (st + pas < a[col].size() and a[col][st + pas].first <= h)
            st += pas;
        pas /= 2;
    }
    return st;
}

int f(int col,int h)
{
    int idx = max_idx_2(col,h);
    if (idx == -1)
        return 0;
    return sp[col][idx];
}

void build(int col)
{
    for (int i = 0; i < poz[col].size(); i++)
    {
        if (i == 0)
        {
            mp_dp0[col][i] = dp0[col][i];
            mp_dp1[col][i] = dp1[col][i];
        }
        else
        {
            mp_dp0[col][i] = max(mp_dp0[col][i - 1],dp0[col][i]);
            mp_dp1[col][i] = max(mp_dp1[col][i - 1],dp1[col][i]);
        }
    }
    for (int i = poz[col].size() - 1; i >= 0; i--)
    {
        if (i + 1 == poz[col].size())
        {
            ms_dp0[col][i] = dp0[col][i];
            ms_dp1[col][i] = dp1[col][i];
        }
        else
        {
            ms_dp0[col][i] = max(ms_dp0[col][i + 1],dp0[col][i]);
            ms_dp1[col][i] = max(ms_dp1[col][i + 1],dp1[col][i]);
        }
    }
    for (int i = 0; i < poz[col].size(); i++)
    {
        int vl = dp1[col][i] - f(col,poz[col][i]);
        if (i == 0)
            lol1[col][i] = vl;
        else
            lol1[col][i] = max(lol1[col][i - 1],vl);
    }
    for (int i = poz[col].size() - 1; i >= 0; i--)
    {
        int vl = max(dp0[col][i],dp1[col][i]) - f(col + 1,poz[col][i]);
        if (i + 1 == poz[col].size())
            lol2[col][i] = vl;
        else
            lol2[col][i] = max(lol2[col][i + 1],vl);
    }
}

/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

int max_weights(integer N, integer M, vector<integer> X, vector<integer> Y, vector<integer> W)
{
    n = N;
    m = M;
    for (int i = 0; i < m; i++)
        swap(X[i],Y[i]);
    for (int i = 0; i < m; i++)
        X[i]++,Y[i]++;
    for (int i = 0; i < m; i++)
        a[Y[i]].push_back({X[i],W[i]});
    for (int i = 0; i < m; i++)
        poz[Y[i]].push_back(X[i] - 1);
    for (int i = 1; i <= n; i++)
    {
        poz[i].push_back(n);
        sort(poz[i].begin(),poz[i].end());
    }
    for (int i = 1; i <= n; i++)
    {
        sort(a[i].begin(),a[i].end());
        sp[i].resize(a[i].size());
        if (a[i].size() == 0)
            continue;
        sp[i][0] = a[i][0].second;
        for (int j = 1; j < sp[i].size(); j++)
            sp[i][j] = sp[i][j - 1] + a[i][j].second;
    }
    for (int i = 1; i <= n; i++)
    {
        int szz = poz[i].size();
        dp0[i].resize(szz);
        dp1[i].resize(szz);
        mp_dp0[i].resize(szz);
        mp_dp1[i].resize(szz);
        ms_dp0[i].resize(szz);
        ms_dp1[i].resize(szz);
        lol1[i].resize(szz);
        lol2[i].resize(szz);
    }
    ///pentru coloana 1, dp-urile sunt 0, doar dau build care imi face chestiile auxiliare
    //cout << 1 << endl;
    build(1);
    //cout << 2 << endl;
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        //cout << f(1,2) << ' ' << lol1[1][0] << endl;
        for (int j = 0; j < poz[i].size(); j++)
        {
            int hpmax = max_idx(i - 1,poz[i][j]);
            if (hpmax != -1)
            {
                dp0[i][j] = max(dp0[i][j],mp_dp0[i - 1][hpmax]);
                dp0[i][j] = max(dp0[i][j],f(i - 1,poz[i][j]) + lol1[i - 1][hpmax]);
            }
            hpmax++;
            if (hpmax != poz[i - 1].size())
                dp0[i][j] = max(dp0[i][j],lol2[i - 1][hpmax] - f(i,poz[i][j]));
        }
        for (int j = 0; j < poz[i].size(); j++)
        {
            int hpmax = max_idx(i - 1,poz[i][j]);
            if (hpmax != -1)
            {
                dp1[i][j] = max(dp1[i][j],mp_dp0[i - 1][hpmax]);
                dp1[i][j] = max(dp1[i][j],f(i - 1,poz[i][j]) + lol1[i - 1][hpmax]);
            }
            hpmax++;
            if (hpmax != poz[i - 1].size())
                dp1[i][j] = max(dp1[i][j],max(ms_dp0[i - 1][hpmax],ms_dp1[i - 1][hpmax]));
        }
        for (int j = 0; j < poz[i].size(); j++)
            ans = max(ans,max(dp0[i][j],dp1[i][j]));
        if (i != n)
            build(i);
    }
    return ans;
}

/**
Daca am pus pana la i, si vreau sa pun la i + 1, am pretty much cateva cazuri:
-daca pun mai jos decat era la i, atunci nu mi se vor mai aduna alea pana unde am pus la i+1
-daca pun mai sus decat era la i, iar am doua cazuri:
-daca pun mai jos decat era la i - 1, nu se intampla mare lucru
-daca pun mai sus decat era la i - 1, e ca si cum as lua toti pestii de la h[i] la h[i + 1], dar sa nu ii fi considerat la i - 1 ofc

In dp-ul curent (pana la i) consider doar ce iau de la 1 la i (eventual, fara i deoarece sunt pe ultimul caz si iau cu urmatorul)

dp0[i][h] = costul de pana la i, daca consider si i ca fiind full pus, si i are inaltimea h (relativ la el)
dp1[i][h] = costul de pana la i, dar cand nu consider i, pentru ca ma bazez ca o sa imi vina i + 1 mai mare

dp0[i][h] vine din doua cazuri:
-daca h' (inaltimea lui i - 1) <= h atunci am dp0[i - 1][h'] si dp1[i - 1][h'] + f(i - 1,h) - f(i - 1,h')
Retin maxime pe prefix din dp0[i][h] si maxime pe prefix din dp1[i][h] - f(i,h)
-daca h' > h, atunci am dp0[i - 1][h'] + f(i,h') - f(i,h) si dp1[i - 1][h'] + f(i,h') - f(i,h)
Retin maxime pe sufix din dp0[i][h] + f(i + 1,h) si maxime pe sufix din dp1[i][h] + f(i + 1,h)

dp1[i][h] vine si el din doua cazuri:
-daca h' <= h atunci am dp0[i - 1][h'] si dp1[i - 1][h'] + f(i - 1,h) - f(i - 1,h')
Cazul e identic cu primul caz de la dp0[i][h]
-daca h' > h, doar am dp0[i - 1][h'] si dp1[i - 1][h']
Retin maxime pe sufix din dp0[i][h] si din dp1[i][h]

h-urile relevante pentru col i sunt (linia unui peste de pe i) - 1 si n, deci total vor fi O(N + M) stari
Sortez si caut binar chestii deci am total O((N + M)log(N + M))
**/

Compilation message (stderr)

fish.cpp: In function 'long long int max_idx(long long int, long long int)':
fish.cpp:24:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if (st + pas < poz[col].size() and poz[col][st + pas] <= h)
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_idx_2(long long int, long long int)':
fish.cpp:36:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (st + pas < a[col].size() and a[col][st + pas].first <= h)
      |             ~~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp: In function 'void build(long long int)':
fish.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < poz[col].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if (i + 1 == poz[col].size())
      |             ~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < poz[col].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
fish.cpp:90:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if (i + 1 == poz[col].size())
      |             ~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(integer, integer, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:129:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int j = 1; j < sp[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
fish.cpp:152:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for (int j = 0; j < poz[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:161:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |             if (hpmax != poz[i - 1].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:164:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int j = 0; j < poz[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
fish.cpp:173:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             if (hpmax != poz[i - 1].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:176:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for (int j = 0; j < poz[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 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