oj.uz

Submission #827351

# Submission time Handle Problem Language Result Execution time Memory
827351 2023-08-16T11:44:04 Z GrindMachine Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 156396 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 = 3e3 + 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];

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

    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 dp[i][j+1][k] = 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:84:9: note: in expansion of macro 'rep'
   84 |         rep(x,sz(a)){
      |         ^~~
fish.cpp:95: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]
   95 |         for(int x = l; x < sz(a); ++x){
      |                          ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 7236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 141680 KB Output is correct
2 Runtime error 57 ms 13704 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141704 KB Output is correct
2 Correct 42 ms 141700 KB Output is correct
3 Correct 42 ms 141720 KB Output is correct
4 Correct 43 ms 141592 KB Output is correct
5 Correct 42 ms 141688 KB Output is correct
6 Correct 43 ms 141628 KB Output is correct
7 Correct 42 ms 141680 KB Output is correct
8 Correct 41 ms 141664 KB Output is correct
9 Correct 44 ms 141744 KB Output is correct
10 Correct 44 ms 141856 KB Output is correct
11 Correct 41 ms 141732 KB Output is correct
12 Correct 42 ms 141752 KB Output is correct
13 Correct 42 ms 141616 KB Output is correct
14 Correct 43 ms 141808 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141704 KB Output is correct
2 Correct 42 ms 141700 KB Output is correct
3 Correct 42 ms 141720 KB Output is correct
4 Correct 43 ms 141592 KB Output is correct
5 Correct 42 ms 141688 KB Output is correct
6 Correct 43 ms 141628 KB Output is correct
7 Correct 42 ms 141680 KB Output is correct
8 Correct 41 ms 141664 KB Output is correct
9 Correct 44 ms 141744 KB Output is correct
10 Correct 44 ms 141856 KB Output is correct
11 Correct 41 ms 141732 KB Output is correct
12 Correct 42 ms 141752 KB Output is correct
13 Correct 42 ms 141616 KB Output is correct
14 Correct 43 ms 141808 KB Output is correct
15 Correct 43 ms 141736 KB Output is correct
16 Correct 44 ms 141768 KB Output is correct
17 Correct 163 ms 144508 KB Output is correct
18 Correct 166 ms 145028 KB Output is correct
19 Correct 117 ms 144968 KB Output is correct
20 Correct 130 ms 144892 KB Output is correct
21 Correct 120 ms 145036 KB Output is correct
22 Correct 312 ms 148084 KB Output is correct
23 Correct 48 ms 142348 KB Output is correct
24 Correct 82 ms 143660 KB Output is correct
25 Correct 50 ms 141772 KB Output is correct
26 Correct 46 ms 142256 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 141704 KB Output is correct
2 Correct 42 ms 141700 KB Output is correct
3 Correct 42 ms 141720 KB Output is correct
4 Correct 43 ms 141592 KB Output is correct
5 Correct 42 ms 141688 KB Output is correct
6 Correct 43 ms 141628 KB Output is correct
7 Correct 42 ms 141680 KB Output is correct
8 Correct 41 ms 141664 KB Output is correct
9 Correct 44 ms 141744 KB Output is correct
10 Correct 44 ms 141856 KB Output is correct
11 Correct 41 ms 141732 KB Output is correct
12 Correct 42 ms 141752 KB Output is correct
13 Correct 42 ms 141616 KB Output is correct
14 Correct 43 ms 141808 KB Output is correct
15 Correct 43 ms 141736 KB Output is correct
16 Correct 44 ms 141768 KB Output is correct
17 Correct 163 ms 144508 KB Output is correct
18 Correct 166 ms 145028 KB Output is correct
19 Correct 117 ms 144968 KB Output is correct
20 Correct 130 ms 144892 KB Output is correct
21 Correct 120 ms 145036 KB Output is correct
22 Correct 312 ms 148084 KB Output is correct
23 Correct 48 ms 142348 KB Output is correct
24 Correct 82 ms 143660 KB Output is correct
25 Correct 50 ms 141772 KB Output is correct
26 Correct 46 ms 142256 KB Output is correct
27 Correct 43 ms 142284 KB Output is correct
28 Execution timed out 1079 ms 156396 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 572 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 7236 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -