oj.uz

Submission #1067673

# Submission time Handle Problem Language Result Execution time Memory
1067673 2024-08-21T00:09:20 Z HorizonWest Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 83120 KB 
#include <bits/stdc++.h>
//#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;
}

long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) 
{
    vector <vector<pair<ll, ll>>> v(n + 7, vector <pair<ll, ll>> ());

    //vector <vector<ll>> v(n, vector <ll> (n+1, 0)); 
    unordered_map <int, unordered_map <int, int>> mp; 

    for(int i = 0; i < m; i++){
        //v[X[i]][Y[i]+1] = W[i];
        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;
        }
    }

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

    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 > 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])); 
            }
        }
    }

    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:113:21: warning: statement has no effect [-Wunused-value]
  113 |                 for(k; k >= 0; k--){
      |                     ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 45500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1028 ms 62688 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40116 KB Output is correct
2 Correct 79 ms 40036 KB Output is correct
3 Correct 300 ms 49584 KB Output is correct
4 Correct 226 ms 49076 KB Output is correct
5 Correct 550 ms 64716 KB Output is correct
6 Correct 591 ms 64120 KB Output is correct
7 Correct 558 ms 64532 KB Output is correct
8 Correct 537 ms 64516 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 50 ms 1008 KB Output is correct
11 Correct 16 ms 604 KB Output is correct
12 Correct 17 ms 860 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 10 ms 604 KB Output is correct

Subtask #5
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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 50 ms 1008 KB Output is correct
11 Correct 16 ms 604 KB Output is correct
12 Correct 17 ms 860 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 254 ms 988 KB Output is correct
17 Execution timed out 1053 ms 10088 KB Time limit exceeded
18 Halted 0 ms 0 KB -

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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 KB Output is correct
9 Correct 7 ms 668 KB Output is correct
10 Correct 50 ms 1008 KB Output is correct
11 Correct 16 ms 604 KB Output is correct
12 Correct 17 ms 860 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 254 ms 988 KB Output is correct
17 Execution timed out 1053 ms 10088 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40116 KB Output is correct
2 Correct 79 ms 40036 KB Output is correct
3 Correct 300 ms 49584 KB Output is correct
4 Correct 226 ms 49076 KB Output is correct
5 Correct 550 ms 64716 KB Output is correct
6 Correct 591 ms 64120 KB Output is correct
7 Correct 558 ms 64532 KB Output is correct
8 Correct 537 ms 64516 KB Output is correct
9 Correct 631 ms 83120 KB Output is correct
10 Correct 756 ms 45476 KB Output is correct
11 Execution timed out 1035 ms 81280 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 45500 KB Time limit exceeded
2 Halted 0 ms 0 KB -