oj.uz

Submission #827354

# Submission time Handle Problem Language Result Execution time Memory
827354 2023-08-16T11:46:28 Z GrindMachine Catfish Farm (IOI22_fish) C++17
40 / 100
 1000 ms 87452 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define conts continue
#define sz(a) a.size()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}

#define debug(x) cout << #x << " = "; cout << x; cout << endl

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "fish.h"

vector<pll> here[N];
ll n;
// ll dp[N][N][2];
map<array<ll,3>,ll> mp;

ll go(ll i, ll j, ll k){
    if(i == n){
        if(k == 0) return 0;
        else return -inf2;
    }

    array<ll,3> ke = {i,j,k};
    if(mp.count(ke)) return mp[ke];

    // if(dp[i][j+1][k] != -1){
    //     return dp[i][j+1][k];
    // }

    auto &a = here[i];
    ll ans = -inf2;

    // take none
    amax(ans,go(i+1,n-1,0));

    if(k == 0){
        // taken guys have height <= j
        pll key = {j+1,-1};
        ll r = upper_bound(all(a),key)-a.begin()-1;
        ll sum = 0;

        rev(x,r,0){
            sum += a[x].ss;
            amax(ans,sum+go(i+1,a[x].ff-1,0));
        }

        // take > j, start 1 phase
        sum = 0;

        rep(x,sz(a)){
            sum += a[x].ss;
            amax(ans,sum+go(i+1,a[x].ff,1));
        }
    }
    else{
        // color at least >= j
        pll key = {j+1,-1};
        ll l = upper_bound(all(a),key)-a.begin();
        ll sum = 0;

        for(int x = l; x < sz(a); ++x){
            sum += a[x].ss;
            amax(ans,sum+go(i+1,a[x].ff,1));
        }
    }

    return mp[ke] = ans;
}

long long max_weights(int n_, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    
    n = n_;
    rep(i,m){
        here[X[i]].pb({Y[i],W[i]});
    }
    rep(i,n){
        sort(all(here[i]));
    }

    // memset(dp,-1,sizeof dp);
    ll ans = go(0,-1,1);
    return ans;
}

Compilation message

fish.cpp: In function 'll go(ll, ll, ll)':
fish.cpp:26:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define rep(i,n) for(int i = 0; i < n; ++i)
      |                                   ^
fish.cpp:88:9: note: in expansion of macro 'rep'
   88 |         rep(x,sz(a)){
      |         ^~~
fish.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int x = l; x < sz(a); ++x){
      |                          ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 33152 KB Output is correct
2 Correct 122 ms 37832 KB Output is correct
3 Correct 26 ms 26012 KB Output is correct
4 Correct 27 ms 26016 KB Output is correct
5 Correct 365 ms 84772 KB Output is correct
6 Correct 387 ms 87452 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26048 KB Output is correct
2 Correct 26 ms 26056 KB Output is correct
3 Correct 98 ms 35000 KB Output is correct
4 Correct 76 ms 34300 KB Output is correct
5 Correct 164 ms 48876 KB Output is correct
6 Correct 152 ms 48108 KB Output is correct
7 Correct 157 ms 48704 KB Output is correct
8 Correct 156 ms 48828 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 8 ms 3156 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2900 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2900 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 8 ms 3156 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2900 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2900 KB Output is correct
15 Correct 1 ms 2772 KB Output is correct
16 Correct 29 ms 3068 KB Output is correct
17 Execution timed out 1088 ms 6976 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 8 ms 3156 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2900 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 3 ms 2900 KB Output is correct
15 Correct 1 ms 2772 KB Output is correct
16 Correct 29 ms 3068 KB Output is correct
17 Execution timed out 1088 ms 6976 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 26048 KB Output is correct
2 Correct 26 ms 26056 KB Output is correct
3 Correct 98 ms 35000 KB Output is correct
4 Correct 76 ms 34300 KB Output is correct
5 Correct 164 ms 48876 KB Output is correct
6 Correct 152 ms 48108 KB Output is correct
7 Correct 157 ms 48704 KB Output is correct
8 Correct 156 ms 48828 KB Output is correct
9 Correct 175 ms 48588 KB Output is correct
10 Correct 232 ms 36712 KB Output is correct
11 Correct 433 ms 70732 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 1 ms 2656 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 26 ms 26060 KB Output is correct
19 Correct 27 ms 26020 KB Output is correct
20 Correct 27 ms 26116 KB Output is correct
21 Correct 26 ms 26068 KB Output is correct
22 Correct 182 ms 48900 KB Output is correct
23 Correct 450 ms 70820 KB Output is correct
24 Correct 468 ms 71268 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 33152 KB Output is correct
2 Correct 122 ms 37832 KB Output is correct
3 Correct 26 ms 26012 KB Output is correct
4 Correct 27 ms 26016 KB Output is correct
5 Correct 365 ms 84772 KB Output is correct
6 Correct 387 ms 87452 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Execution timed out 1078 ms 42804 KB Time limit exceeded
9 Halted 0 ms 0 KB -