oj.uz

Submission #1069492

# Submission time Handle Problem Language Result Execution time Memory
1069492 2024-08-22T02:48:00 Z HorizonWest Catfish Farm (IOI22_fish) C++17
64 / 100
 1000 ms 171448 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 <unordered_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, unordered_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 201 ms 55576 KB Output is correct
2 Correct 227 ms 65964 KB Output is correct
3 Correct 56 ms 36272 KB Output is correct
4 Correct 69 ms 36304 KB Output is correct
5 Execution timed out 1090 ms 171448 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 348 KB Output is correct
2 Correct 303 ms 68036 KB Output is correct
3 Correct 352 ms 76624 KB Output is correct
4 Correct 192 ms 55496 KB Output is correct
5 Correct 234 ms 66124 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 57 ms 36532 KB Output is correct
11 Correct 54 ms 36272 KB Output is correct
12 Correct 247 ms 61300 KB Output is correct
13 Correct 302 ms 73800 KB Output is correct
14 Correct 228 ms 58356 KB Output is correct
15 Correct 199 ms 55496 KB Output is correct
16 Correct 220 ms 58828 KB Output is correct
17 Correct 264 ms 67308 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 37040 KB Output is correct
2 Correct 60 ms 36784 KB Output is correct
3 Correct 89 ms 37564 KB Output is correct
4 Correct 82 ms 40116 KB Output is correct
5 Correct 132 ms 43336 KB Output is correct
6 Correct 125 ms 43956 KB Output is correct
7 Correct 126 ms 43440 KB Output is correct
8 Correct 128 ms 43444 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 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 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 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 43 ms 7612 KB Output is correct
18 Correct 35 ms 6140 KB Output is correct
19 Correct 41 ms 7332 KB Output is correct
20 Correct 37 ms 5712 KB Output is correct
21 Correct 41 ms 5460 KB Output is correct
22 Correct 69 ms 10436 KB Output is correct
23 Correct 18 ms 4188 KB Output is correct
24 Correct 44 ms 8368 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 13 ms 2908 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 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 43 ms 7612 KB Output is correct
18 Correct 35 ms 6140 KB Output is correct
19 Correct 41 ms 7332 KB Output is correct
20 Correct 37 ms 5712 KB Output is correct
21 Correct 41 ms 5460 KB Output is correct
22 Correct 69 ms 10436 KB Output is correct
23 Correct 18 ms 4188 KB Output is correct
24 Correct 44 ms 8368 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 13 ms 2908 KB Output is correct
27 Correct 9 ms 2652 KB Output is correct
28 Correct 217 ms 27704 KB Output is correct
29 Correct 596 ms 65640 KB Output is correct
30 Execution timed out 1034 ms 142164 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 37040 KB Output is correct
2 Correct 60 ms 36784 KB Output is correct
3 Correct 89 ms 37564 KB Output is correct
4 Correct 82 ms 40116 KB Output is correct
5 Correct 132 ms 43336 KB Output is correct
6 Correct 125 ms 43956 KB Output is correct
7 Correct 126 ms 43440 KB Output is correct
8 Correct 128 ms 43444 KB Output is correct
9 Correct 411 ms 79784 KB Output is correct
10 Correct 96 ms 26548 KB Output is correct
11 Correct 224 ms 52656 KB Output is correct
12 Correct 0 ms 344 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 54 ms 36900 KB Output is correct
19 Correct 64 ms 36528 KB Output is correct
20 Correct 64 ms 36836 KB Output is correct
21 Correct 60 ms 36788 KB Output is correct
22 Correct 402 ms 77732 KB Output is correct
23 Correct 488 ms 77228 KB Output is correct
24 Correct 603 ms 86192 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 55576 KB Output is correct
2 Correct 227 ms 65964 KB Output is correct
3 Correct 56 ms 36272 KB Output is correct
4 Correct 69 ms 36304 KB Output is correct
5 Execution timed out 1090 ms 171448 KB Time limit exceeded
6 Halted 0 ms 0 KB -