oj.uz

Submission #1069162

# Submission time Handle Problem Language Result Execution time Memory
1069162 2024-08-21T16:40:45 Z HorizonWest Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 938780 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 <vector<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;
}
 
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, vector <int> (n + 1, 0)); 
    N = n;

    for(int i = 0; i < n; i++){
        for(int j = 0; j <= n; j++){
            v[i].push_back({ j, 0 });
        }
    }
 
    for(int i = 0; i < m; i++){
        v[X[i]][Y[i]+1].sd = 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;
        }
    }
 
    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 < (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 < (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:168:21: warning: statement has no effect [-Wunused-value]
  168 |                 for(k; k >= 0; k--){
      |                     ^
fish.cpp:192:21: warning: statement has no effect [-Wunused-value]
  192 |                 for(k; k < (ll) v[i-1].size(); k++)
      |                     ^

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 9.0

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

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 1 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 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 30 ms 3332 KB Output is correct
10 Correct 242 ms 8528 KB Output is correct
11 Correct 29 ms 1880 KB Output is correct
12 Correct 211 ms 8276 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 216 ms 5720 KB Output is correct

Subtask #5
21.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 1 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 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 30 ms 3332 KB Output is correct
10 Correct 242 ms 8528 KB Output is correct
11 Correct 29 ms 1880 KB Output is correct
12 Correct 211 ms 8276 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 216 ms 5720 KB Output is correct
15 Correct 207 ms 8344 KB Output is correct
16 Correct 7 ms 972 KB Output is correct
17 Correct 218 ms 9484 KB Output is correct
18 Correct 215 ms 9376 KB Output is correct
19 Correct 225 ms 6804 KB Output is correct
20 Correct 213 ms 9300 KB Output is correct
21 Correct 219 ms 6852 KB Output is correct
22 Correct 221 ms 10568 KB Output is correct
23 Correct 211 ms 5992 KB Output is correct
24 Correct 214 ms 8952 KB Output is correct
25 Correct 211 ms 8276 KB Output is correct
26 Correct 205 ms 8592 KB Output is correct

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 1 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 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 30 ms 3332 KB Output is correct
10 Correct 242 ms 8528 KB Output is correct
11 Correct 29 ms 1880 KB Output is correct
12 Correct 211 ms 8276 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 216 ms 5720 KB Output is correct
15 Correct 207 ms 8344 KB Output is correct
16 Correct 7 ms 972 KB Output is correct
17 Correct 218 ms 9484 KB Output is correct
18 Correct 215 ms 9376 KB Output is correct
19 Correct 225 ms 6804 KB Output is correct
20 Correct 213 ms 9300 KB Output is correct
21 Correct 219 ms 6852 KB Output is correct
22 Correct 221 ms 10568 KB Output is correct
23 Correct 211 ms 5992 KB Output is correct
24 Correct 214 ms 8952 KB Output is correct
25 Correct 211 ms 8276 KB Output is correct
26 Correct 205 ms 8592 KB Output is correct
27 Execution timed out 1072 ms 189268 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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