oj.uz

Submission #1069491

# Submission time Handle Problem Language Result Execution time Memory
1069491 2024-08-22T02:46:03 Z HorizonWest Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 128240 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
//#include "fish.h"
using namespace std;
 
#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
 
const int Max = 1e6 + 7, Inf = 1e9 + 7;
 
void print(bool x) { cout << (x ? "YES" : "NO") << endl; }
 
string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

vector <vector<pair<ll, ll>>> v;
vector <map<int, int>> mp;
int N;//, mp[3007][3007];

ll C(int i, int j, int k)
{
    if(i >= 0 && i < N)
        return max(0LL, v[i][mp[i][j]].sd - v[i][mp[i][k]].sd);
    else 
        return 0LL;
}

void add(int i, int y, int w)
{
    if(i < 0 || i >= N) 
        return;
    if(mp[i][y] == 0){
        v[i].push_back({ y, 0 });
        mp[i][y] = v[i].size();
    }
    v[i][mp[i][y] - 1].sd += w;
}
 
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) 
{   
    v.clear(); mp.clear();
    v.assign(n + 7, vector <pair<ll, ll>> ());
    mp.assign(n + 1, map<int, int> ()); 
    N = n;
 
    for(int i = 0; i < m; i++){
        //v[X[i]][Y[i]+1].sd = W[i];

        add(X[i], Y[i]+1, W[i]);
        add(X[i] - 2, Y[i]+1, 0);
        add(X[i] - 1, Y[i]+1, 0);
        add(X[i] + 1, Y[i]+1, 0);
        add(X[i] + 2, Y[i]+1, 0);
        //v[X[i]].push_back({ Y[i] + 1, W[i] });
        //if(X[i] > 0) v[X[i]-1].push_back({ Y[i] + 1, 0 });
        //if(X[i] > 1) v[X[i]-2].push_back({ Y[i] + 1, 0 });
        //if(X[i] < n) v[X[i]+1].push_back({ Y[i] + 1, 0 });
        //if(X[i] < n) v[X[i]+2].push_back({ Y[i] + 1, 0 });
    }
 
    for(int i = 0; i < n; i++)
    {
        v[i].push_back({ 0, 0 }); sort(all(v[i]));
 
        for(int j = 0; j < (int) v[i].size(); j++){
            if (j != 0) v[i][j].sd += v[i][j-1].sd;
            mp[i][v[i][j].fs] = j;
        }
    }
 
    vector <vector<ll>> dp1, dp2; ll ans = 0; 
 
    for(int i = 0; i < n; i++)
    {   
        dp1.push_back(vector <ll> (v[i].size(), 0));
        dp2.push_back(vector <ll> (v[i].size(), 0));
 
        for(int j = 0; j < (int) v[i].size(); j++)
        {
            int hj = v[i][j].fs;
 
            dp1[i][j] = C(i-1, hj, 0) + C(i+1, hj, 0);
            dp2[i][j] = C(i-1, hj, 0) + C(i+1, hj, 0);
 
            /*if(i > 1){
                for(int k = 0; k < (int) v[i-2].size(); k++){
                    int hk = v[i-2][k].fs; 
                    dp1[i][j] = max(dp1[i][j], (i > 1 ? dp2[i-2][k] : 0LL) + C(i-1, hj, hk) + C(i+1, hj, 0));
                }
            }*/
 
            /*if(i > 0){
                for(int k = 0; k < (int) v[i-1].size(); k++){    
                    int hk = v[i-1][k].fs; 
                    dp1[i][j] = max(dp1[i][j], (i != 0 ? dp1[i-1][k] : 0) + C(i-1, hj, hk) + C(i+1, hj, 0) - C(i, hk, 0));
                }
            
                for(int k = 0; k < (int) v[i-1].size(); k++){
                    int hk = v[i-1][k].fs; 
                    dp2[i][j] = max(dp2[i][j], (i != 0 ? dp1[i-1][k] : 0) - C(i, hj, 0) + C(i+1, hj, 0));
                    dp2[i][j] = max(dp2[i][j], (i != 0 ? dp2[i-1][k] : 0) - C(i, hj, 0) + C(i+1, hj, 0));
                }
            }*/
 
            ans = max(ans, max(dp1[i][j], dp2[i][j])); 
        } 

        if(i > 1)
        {
            ll k = 0, mx = 0, tmp = 0;

            for(k = 0; k < (int) v[i-2].size(); k++){
                tmp = max(tmp, dp2[i-2][k]); 
            }

            for(int j = 0; j < (int) v[i].size(); j++)
            {
                int hj = v[i][j].fs; 
 
                for(k; k < (int) v[i-2].size(); k++)
                {
                    if(v[i-2][k].fs <= v[i][j].fs)
                    {
                        int hk = v[i-2][k].fs, hx = v[i-2][mx].fs; 

                        ll val1 = dp2[i-2][mx] + C(i-1, hj, hx) + C(i+1, hj, 0);
                        ll val2 = dp2[i-2][k] + C(i-1, hj, hk) + C(i+1, hj, 0);

                        if(val1 < val2){
                            mx = k;
                        }
                    } else break;
                }

                int hx = v[i-2][mx].fs;
                dp1[i][j] = max(dp1[i][j], dp2[i-2][mx] + C(i-1, hj, hx) + C(i+1, hj, 0));
                dp1[i][j] = max(dp1[i][j], tmp + C(i+1, hj, 0)); 

                ans = max(ans, dp1[i][j]); 
            }
        }
 
        if(i > 0)
        {
            ll k = v[i-1].size() - 1, mx = 0; 
            for(int j = (int) v[i].size() - 1; j >= 0; j--)
            {
                int hj = v[i][j].fs;
                for(k; k >= 0; k--){
                    if(v[i-1][k].fs >= v[i][j].fs){
                        mx = max(mx, dp1[i-1][k]); 
                        mx = max(mx, dp2[i-1][k]); 
                    } else break;
                }
 
                dp2[i][j] = max(dp2[i][j], mx - C(i, hj, 0) + C(i+1, hj, 0));
 
                ans = max(ans, max(dp1[i][j], dp2[i][j])); 
            }

            ll tmp = 0;
            for(k = 0; k < (int) v[i-1].size(); k++){
                int hk = v[i-1][k].fs;
                tmp = max(tmp, dp1[i-1][k] - C(i, hk, 0)); 
            }

            k = 0; mx = 0; 
            
            for(int j = 0; j < (int) v[i].size(); j++)
            {
                int hj = v[i][j].fs; 
 
                for(k; k < (int) v[i-1].size(); k++)
                {
                    if(v[i-1][k].fs <= v[i][j].fs)
                    {
                        int hk = v[i-1][k].fs; 
                        mx = max(mx + (v[i-1][k].sd - v[i-1][max(0LL, k-1)].sd),
                                 dp1[i-1][k] - C(i, hk, 0));
                    } else break;
                }

                dp1[i][j] = max(dp1[i][j], mx + C(i+1, hj, 0));
                dp1[i][j] = max(dp1[i][j], tmp + C(i+1, hj, 0)); 
                dp2[i][j] = max(dp2[i][j], dp1[i][j]);

                ans = max(ans, max(dp1[i][j], dp2[i][j])); 
            }
        }
    }
 
    return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:150:21: warning: statement has no effect [-Wunused-value]
  150 |                 for(k; k < (int) v[i-2].size(); k++)
      |                     ^
fish.cpp:179:21: warning: statement has no effect [-Wunused-value]
  179 |                 for(k; k >= 0; k--){
      |                     ^
fish.cpp:203:21: warning: statement has no effect [-Wunused-value]
  203 |                 for(k; k < (int) v[i-1].size(); k++)
      |                     ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 48280 KB Output is correct
2 Correct 449 ms 57356 KB Output is correct
3 Correct 31 ms 26036 KB Output is correct
4 Correct 33 ms 26800 KB Output is correct
5 Execution timed out 1081 ms 128240 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 614 ms 58764 KB Output is correct
3 Correct 802 ms 70668 KB Output is correct
4 Correct 370 ms 50328 KB Output is correct
5 Correct 468 ms 58524 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 32 ms 26532 KB Output is correct
11 Correct 32 ms 26040 KB Output is correct
12 Correct 470 ms 56204 KB Output is correct
13 Correct 672 ms 66324 KB Output is correct
14 Correct 409 ms 53648 KB Output is correct
15 Correct 334 ms 47680 KB Output is correct
16 Correct 446 ms 53396 KB Output is correct
17 Correct 496 ms 58612 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 26036 KB Output is correct
2 Correct 40 ms 26152 KB Output is correct
3 Correct 70 ms 28976 KB Output is correct
4 Correct 54 ms 30776 KB Output is correct
5 Correct 84 ms 35384 KB Output is correct
6 Correct 84 ms 35292 KB Output is correct
7 Correct 87 ms 35384 KB Output is correct
8 Correct 93 ms 34852 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 540 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 644 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 540 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 644 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 103 ms 7760 KB Output is correct
18 Correct 85 ms 6224 KB Output is correct
19 Correct 90 ms 7508 KB Output is correct
20 Correct 81 ms 5708 KB Output is correct
21 Correct 72 ms 5476 KB Output is correct
22 Correct 164 ms 10568 KB Output is correct
23 Correct 42 ms 4180 KB Output is correct
24 Correct 97 ms 8448 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 30 ms 3084 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 540 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 644 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 4 ms 604 KB Output is correct
17 Correct 103 ms 7760 KB Output is correct
18 Correct 85 ms 6224 KB Output is correct
19 Correct 90 ms 7508 KB Output is correct
20 Correct 81 ms 5708 KB Output is correct
21 Correct 72 ms 5476 KB Output is correct
22 Correct 164 ms 10568 KB Output is correct
23 Correct 42 ms 4180 KB Output is correct
24 Correct 97 ms 8448 KB Output is correct
25 Correct 3 ms 604 KB Output is correct
26 Correct 30 ms 3084 KB Output is correct
27 Correct 7 ms 2648 KB Output is correct
28 Correct 559 ms 32596 KB Output is correct
29 Execution timed out 1022 ms 63824 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 26036 KB Output is correct
2 Correct 40 ms 26152 KB Output is correct
3 Correct 70 ms 28976 KB Output is correct
4 Correct 54 ms 30776 KB Output is correct
5 Correct 84 ms 35384 KB Output is correct
6 Correct 84 ms 35292 KB Output is correct
7 Correct 87 ms 35384 KB Output is correct
8 Correct 93 ms 34852 KB Output is correct
9 Correct 381 ms 81620 KB Output is correct
10 Correct 79 ms 22660 KB Output is correct
11 Correct 164 ms 45100 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 31 ms 26364 KB Output is correct
19 Correct 31 ms 26288 KB Output is correct
20 Correct 31 ms 26424 KB Output is correct
21 Correct 37 ms 26044 KB Output is correct
22 Correct 382 ms 79280 KB Output is correct
23 Correct 440 ms 77140 KB Output is correct
24 Correct 520 ms 89524 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 48280 KB Output is correct
2 Correct 449 ms 57356 KB Output is correct
3 Correct 31 ms 26036 KB Output is correct
4 Correct 33 ms 26800 KB Output is correct
5 Execution timed out 1081 ms 128240 KB Time limit exceeded
6 Halted 0 ms 0 KB -