oj.uz

Submission #837005

# Submission time Handle Problem Language Result Execution time Memory
837005 2023-08-24T19:37:22 Z ALeonidou Catfish Farm (IOI22_fish) C++17
23 / 100
 117 ms 71480 KB 
/*
IOI 2022 "Catfish" Solution for Subtask 4 (32%)
Time Complexity: O(N * Y^3)
*/

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
#define ll int
#define sz(x) (ll)x.size()
#define F first
#define S second
#define pb push_back
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

typedef vector <ll> vi;
typedef vector <long long > vl;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;

void printVct(vl &v, string s = ""){
    cout<<s<<": ";
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

#define printArr2D(arr, n, m, s) cout<<s<<": "<<endl; for (ll i=0; i<n; i++){ cout<<i<<": "; for (ll j =0; j<m; j++){cout<<arr[i][j]<<" ";}cout<<endl;} cout<<endl;

#define N 100001
#define MAXC 5 // 5 cases

ll n,m;
long long dp[N+1][MAXC+1][MAXC+1];
vector <vii> arr;
vector <vi> s;

void printDP(ll l = 0, ll r = MAXC-1){
    for (ll k=l; k<=r; k++){
        cout<<"k: "<<k<<endl;
        for (ll i = 0; i<n; i++){
            cout<<i<<": ";
            for (ll j =0; j<MAXC; j++){
                cout<<dp[i][j][k];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
}

long long calc(ll u, ll l, ll r){ 
    long long sum = 0;
    for (ll i=0; i<sz(arr[u]); i++){
        if (arr[u][i].F >= l && arr[u][i].F <= r){
            sum += arr[u][i].S;
        }
    }
    return sum;
}

long long solve(){
    //prep line 0
    for (ll j =0; j<MAXC; j++){
        for (ll k =0; k<MAXC; k++){
            dp[0][j][k] = 0;
        }
    }
    
    //prep line 1
    for (ll j =0; j<MAXC; j++){
        for (ll k =0; k<MAXC; k++){
            ll new_j = s[1][j], new_k = s[0][k];
            if (new_j == new_k) dp[1][j][k] = 0;
            else if (new_j > new_k){
                dp[1][j][k] = calc(0, new_k+1, new_j);
            }
            else{
                dp[1][j][k] = calc(1, new_j+1, new_k);
            }
        }
    }

    // printDP();

    //solve
    for (ll i =2; i<n; i++){
        for (ll j = 0; j<MAXC; j++){
            for (ll k =0; k<MAXC; k++){
                long long ans = 0, c;
                ll new_j = s[i][j], new_k = s[i-1][k], new_y;
                
                if (new_j > new_k){
                    for (ll y = 0; y<MAXC; y++){
                        new_y = s[i-2][y];
                        if (new_y <= new_k){
                            c = dp[i-1][k][y] + calc(i-1,new_k+1,new_j);
                        }
                        else if (new_y < new_j){
                            c = dp[i-1][k][y] + calc(i-1,new_y+1,new_j);
                        }
                        else{
                            c = dp[i-1][k][y];
                        }
                        ans = max(ans, c);
                    }
                }
                else{   // j <= k
                    for (ll y = 0; y<MAXC; y++){
                        ans = max(ans, dp[i-1][k][y]);
                    }
                    if (new_j < new_k){
                        ans += calc(i, new_j+1, new_k);
                    }
                }
                dp[i][j][k] = ans;
            }
        }
    }

    // printDP();

    long long ans =0;
    for (ll i =0; i<n; i++){
        for (ll j =0; j<MAXC; j++){
            for (ll k =0; k<MAXC; k++){
                ans = max(ans, dp[i][j][k]);
            }
        }
    }

    return ans;
}

long long max_weights(int NN, int M, vi X, vi Y, vi W) {
    n= NN, m =M;

    //step 1:
    arr.assign(n, vii());
    for (ll i=0; i<m; i++){
        arr[X[i]].pb(ii(Y[i]+1, W[i]));
    }

    // for (ll i=0; i<2; i++){
    //     for (ll j = 0; j<n; j++){
    //         if (sz(arr[j]) > i) cout<<"("<<arr[j][i].F<<" "<<arr[j][i].S<<"), ";
    //         else cout<<"(-,-), ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;

    //step 2:
    s.assign(n, vi(5,0));
    for (ll i=0; i<n; i++){
        ll idx = 0;
        if (i != 0){
            for (ll j = 0; j<sz(arr[i-1]); j++){
                s[i][idx] = arr[i-1][j].F;
                idx++;
            }
        }
        if (i != n-1){
            for (ll j = 0; j<sz(arr[i+1]); j++){
                s[i][idx] = arr[i+1][j].F;
                idx++;
            }
        }
        sort(s[i].begin(), s[i].end());
    }

    // printArr2D(s,n,MAXC,"s");

    long long ans = solve();
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 67420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 107 ms 71480 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 36324 KB Output is correct
2 Correct 29 ms 36308 KB Output is correct
3 Correct 42 ms 36520 KB Output is correct
4 Correct 39 ms 38880 KB Output is correct
5 Correct 61 ms 43340 KB Output is correct
6 Correct 74 ms 42708 KB Output is correct
7 Correct 68 ms 43224 KB Output is correct
8 Correct 63 ms 43332 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 596 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 36324 KB Output is correct
2 Correct 29 ms 36308 KB Output is correct
3 Correct 42 ms 36520 KB Output is correct
4 Correct 39 ms 38880 KB Output is correct
5 Correct 61 ms 43340 KB Output is correct
6 Correct 74 ms 42708 KB Output is correct
7 Correct 68 ms 43224 KB Output is correct
8 Correct 63 ms 43332 KB Output is correct
9 Correct 61 ms 43144 KB Output is correct
10 Correct 47 ms 23948 KB Output is correct
11 Correct 97 ms 47572 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 312 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 24 ms 36308 KB Output is correct
19 Correct 26 ms 36300 KB Output is correct
20 Correct 33 ms 36304 KB Output is correct
21 Correct 26 ms 36312 KB Output is correct
22 Correct 95 ms 42828 KB Output is correct
23 Correct 117 ms 47536 KB Output is correct
24 Correct 109 ms 48204 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 67420 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -