oj.uz

Submission #1069486

# Submission time Handle Problem Language Result Execution time Memory
1069486 2024-08-22T02:32:53 Z HorizonWest Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 192884 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 <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, 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);
        add(X[i] + 3, Y[i]+1, 0);
        add(X[i] + 4, Y[i]+1, 0);
        add(X[i] - 3, Y[i]+1, 0);
        add(X[i] - 4, 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++)
    {
        add(i, 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, 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)); 
                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:154:21: warning: statement has no effect [-Wunused-value]
  154 |                 for(k; k < (int) v[i-2].size(); k++)
      |                     ^
fish.cpp:183:21: warning: statement has no effect [-Wunused-value]
  183 |                 for(k; k >= 0; k--){
      |                     ^
fish.cpp:207:21: warning: statement has no effect [-Wunused-value]
  207 |                 for(k; k < (int) v[i-1].size(); k++)
      |                     ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 61868 KB Output is correct
2 Correct 986 ms 74628 KB Output is correct
3 Correct 40 ms 26492 KB Output is correct
4 Correct 38 ms 26848 KB Output is correct
5 Execution timed out 1067 ms 192884 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 26648 KB Output is correct
2 Correct 41 ms 26544 KB Output is correct
3 Correct 77 ms 30064 KB Output is correct
4 Correct 70 ms 31524 KB Output is correct
5 Correct 110 ms 36316 KB Output is correct
6 Correct 105 ms 35892 KB Output is correct
7 Correct 162 ms 36376 KB Output is correct
8 Correct 108 ms 36872 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 388 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 432 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 388 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 432 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 6 ms 836 KB Output is correct
17 Correct 154 ms 8700 KB Output is correct
18 Correct 123 ms 6428 KB Output is correct
19 Correct 154 ms 9044 KB Output is correct
20 Correct 108 ms 5716 KB Output is correct
21 Correct 100 ms 5460 KB Output is correct
22 Correct 231 ms 10576 KB Output is correct
23 Incorrect 77 ms 5456 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3061028647437'
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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 388 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 432 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 6 ms 836 KB Output is correct
17 Correct 154 ms 8700 KB Output is correct
18 Correct 123 ms 6428 KB Output is correct
19 Correct 154 ms 9044 KB Output is correct
20 Correct 108 ms 5716 KB Output is correct
21 Correct 100 ms 5460 KB Output is correct
22 Correct 231 ms 10576 KB Output is correct
23 Incorrect 77 ms 5456 KB 1st lines differ - on the 1st token, expected: '3061077668538', found: '3061028647437'
24 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 26648 KB Output is correct
2 Correct 41 ms 26544 KB Output is correct
3 Correct 77 ms 30064 KB Output is correct
4 Correct 70 ms 31524 KB Output is correct
5 Correct 110 ms 36316 KB Output is correct
6 Correct 105 ms 35892 KB Output is correct
7 Correct 162 ms 36376 KB Output is correct
8 Correct 108 ms 36872 KB Output is correct
9 Correct 870 ms 120300 KB Output is correct
10 Correct 106 ms 24216 KB Output is correct
11 Correct 210 ms 48716 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 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 1 ms 348 KB Output is correct
18 Correct 38 ms 26292 KB Output is correct
19 Correct 35 ms 26388 KB Output is correct
20 Correct 35 ms 26208 KB Output is correct
21 Correct 40 ms 26536 KB Output is correct
22 Incorrect 919 ms 115896 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45561643450621'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 61868 KB Output is correct
2 Correct 986 ms 74628 KB Output is correct
3 Correct 40 ms 26492 KB Output is correct
4 Correct 38 ms 26848 KB Output is correct
5 Execution timed out 1067 ms 192884 KB Time limit exceeded
6 Halted 0 ms 0 KB -