oj.uz

Submission #1067815

# Submission time Handle Problem Language Result Execution time Memory
1067815 2024-08-21T03:51:29 Z HorizonWest Catfish Farm (IOI22_fish) C++17
29 / 100
 1000 ms 196676 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;
}
 
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 > 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 < (ll) 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-1][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 < (ll) v[i-1].size(); k++)
                {
                    if(v[i-1][k].fs <= v[i][j].fs)
                    {
                        int hk = v[i-1][k].fs, hx = v[i-1][mx].fs; 

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

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

                int hx = v[i-1][mx].fs;
                dp1[i][j] = max(dp1[i][j], dp1[i-1][mx] + C(i-1, hj, hx) + C(i+1, hj, 0) - C(i, hx, 0));
                dp1[i][j] = max(dp1[i][j], tmp + 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:130:21: warning: statement has no effect [-Wunused-value]
  130 |                 for(k; k < (ll) v[i-2].size(); k++)
      |                     ^
fish.cpp:159:21: warning: statement has no effect [-Wunused-value]
  159 |                 for(k; k >= 0; k--){
      |                     ^
fish.cpp:183:21: warning: statement has no effect [-Wunused-value]
  183 |                 for(k; k < (ll) v[i-1].size(); k++)
      |                     ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 59812 KB Output is correct
2 Correct 255 ms 71584 KB Output is correct
3 Correct 105 ms 40120 KB Output is correct
4 Correct 84 ms 40008 KB Output is correct
5 Execution timed out 1010 ms 196676 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 384 ms 81940 KB Output is correct
3 Correct 462 ms 93708 KB Output is correct
4 Correct 200 ms 59816 KB Output is correct
5 Correct 242 ms 71332 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 95 ms 40116 KB Output is correct
11 Correct 100 ms 39924 KB Output is correct
12 Correct 277 ms 65680 KB Output is correct
13 Correct 331 ms 79084 KB Output is correct
14 Correct 236 ms 62876 KB Output is correct
15 Correct 255 ms 64460 KB Output is correct
16 Correct 245 ms 62940 KB Output is correct
17 Correct 270 ms 72332 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 39996 KB Output is correct
2 Correct 103 ms 40120 KB Output is correct
3 Correct 321 ms 49592 KB Output is correct
4 Correct 235 ms 49156 KB Output is correct
5 Correct 390 ms 64692 KB Output is correct
6 Correct 382 ms 63920 KB Output is correct
7 Correct 389 ms 64688 KB Output is correct
8 Correct 402 ms 64688 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 2 ms 440 KB Output is correct
10 Correct 8 ms 1116 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 604 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 2 ms 440 KB Output is correct
10 Correct 8 ms 1116 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 608 KB Output is correct
16 Correct 6 ms 1116 KB Output is correct
17 Correct 127 ms 13652 KB Output is correct
18 Correct 119 ms 12884 KB Output is correct
19 Correct 125 ms 13652 KB Output is correct
20 Correct 119 ms 12624 KB Output is correct
21 Correct 122 ms 12624 KB Output is correct
22 Correct 254 ms 24108 KB Output is correct
23 Incorrect 30 ms 4952 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3051082366309'
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 2 ms 440 KB Output is correct
10 Correct 8 ms 1116 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 2 ms 608 KB Output is correct
16 Correct 6 ms 1116 KB Output is correct
17 Correct 127 ms 13652 KB Output is correct
18 Correct 119 ms 12884 KB Output is correct
19 Correct 125 ms 13652 KB Output is correct
20 Correct 119 ms 12624 KB Output is correct
21 Correct 122 ms 12624 KB Output is correct
22 Correct 254 ms 24108 KB Output is correct
23 Incorrect 30 ms 4952 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3051082366309'
24 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 39996 KB Output is correct
2 Correct 103 ms 40120 KB Output is correct
3 Correct 321 ms 49592 KB Output is correct
4 Correct 235 ms 49156 KB Output is correct
5 Correct 390 ms 64692 KB Output is correct
6 Correct 382 ms 63920 KB Output is correct
7 Correct 389 ms 64688 KB Output is correct
8 Correct 402 ms 64688 KB Output is correct
9 Correct 457 ms 83124 KB Output is correct
10 Correct 320 ms 45656 KB Output is correct
11 Correct 663 ms 90796 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 400 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 436 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 106 ms 40020 KB Output is correct
19 Correct 86 ms 40116 KB Output is correct
20 Correct 101 ms 40120 KB Output is correct
21 Correct 100 ms 40120 KB Output is correct
22 Incorrect 538 ms 82696 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45561005144564'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 59812 KB Output is correct
2 Correct 255 ms 71584 KB Output is correct
3 Correct 105 ms 40120 KB Output is correct
4 Correct 84 ms 40008 KB Output is correct
5 Execution timed out 1010 ms 196676 KB Time limit exceeded
6 Halted 0 ms 0 KB -