oj.uz

Submission #1067772

# Submission time Handle Problem Language Result Execution time Memory
1067772 2024-08-21T03:03:18 Z HorizonWest Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 83132 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 > 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])); 
            }
 
            k = 0; mx = 0;
            for(int j = 0; j < (int) v[i].size(); j++)
            {
                int hj = v[i][j].fs; 
 
                for(k = 0; 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));
 
                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:124:21: warning: statement has no effect [-Wunused-value]
  124 |                 for(k; k >= 0; k--){
      |                     ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 44204 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 1098 ms 59748 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40120 KB Output is correct
2 Correct 94 ms 40120 KB Output is correct
3 Correct 470 ms 48564 KB Output is correct
4 Correct 331 ms 49072 KB Output is correct
5 Correct 770 ms 64736 KB Output is correct
6 Correct 815 ms 64016 KB Output is correct
7 Correct 782 ms 64692 KB Output is correct
8 Correct 805 ms 64692 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 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 11 ms 612 KB Output is correct
10 Correct 79 ms 1108 KB Output is correct
11 Correct 18 ms 856 KB Output is correct
12 Correct 22 ms 860 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 15 ms 820 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 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 11 ms 612 KB Output is correct
10 Correct 79 ms 1108 KB Output is correct
11 Correct 18 ms 856 KB Output is correct
12 Correct 22 ms 860 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 15 ms 820 KB Output is correct
15 Correct 3 ms 856 KB Output is correct
16 Correct 416 ms 1104 KB Output is correct
17 Execution timed out 1038 ms 10064 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 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 11 ms 612 KB Output is correct
10 Correct 79 ms 1108 KB Output is correct
11 Correct 18 ms 856 KB Output is correct
12 Correct 22 ms 860 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 15 ms 820 KB Output is correct
15 Correct 3 ms 856 KB Output is correct
16 Correct 416 ms 1104 KB Output is correct
17 Execution timed out 1038 ms 10064 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40120 KB Output is correct
2 Correct 94 ms 40120 KB Output is correct
3 Correct 470 ms 48564 KB Output is correct
4 Correct 331 ms 49072 KB Output is correct
5 Correct 770 ms 64736 KB Output is correct
6 Correct 815 ms 64016 KB Output is correct
7 Correct 782 ms 64692 KB Output is correct
8 Correct 805 ms 64692 KB Output is correct
9 Correct 885 ms 83132 KB Output is correct
10 Execution timed out 1071 ms 45652 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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