oj.uz

Submission #1067832

# Submission time Handle Problem Language Result Execution time Memory
1067832 2024-08-21T04:09:24 Z HorizonWest Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 54992 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)); 
    map <int, 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 = 0; 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: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 Execution timed out 1018 ms 42504 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 348 KB Output is correct
2 Execution timed out 1093 ms 54992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 30796 KB Output is correct
2 Correct 327 ms 30888 KB Output is correct
3 Correct 805 ms 41136 KB Output is correct
4 Correct 706 ms 39988 KB Output is correct
5 Execution timed out 1068 ms 46452 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 344 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 7 ms 648 KB Output is correct
10 Correct 40 ms 1108 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Incorrect 15 ms 860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '450658355118'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 344 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 7 ms 648 KB Output is correct
10 Correct 40 ms 1108 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Incorrect 15 ms 860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '450658355118'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 344 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 7 ms 648 KB Output is correct
10 Correct 40 ms 1108 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Incorrect 15 ms 860 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '450658355118'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 30796 KB Output is correct
2 Correct 327 ms 30888 KB Output is correct
3 Correct 805 ms 41136 KB Output is correct
4 Correct 706 ms 39988 KB Output is correct
5 Execution timed out 1068 ms 46452 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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