oj.uz

Submission #1049768

# Submission time Handle Problem Language Result Execution time Memory
1049768 2024-08-09T04:50:33 Z wXs Catfish Farm (IOI22_fish) C++17
6 / 100
 252 ms 153944 KB 
#include <cstdio>
#include <cassert>
#include <vector>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pi;
#define all(x) x.begin(),x.end()
#define rll(x) x.rbegin(), x.rend()
struct segtree{
    vector<ll> tree;
    segtree(): tree(404040){}
    void upd(ll node, ll s, ll e, ll i, ll d){
        if(e<i or i<s)return;
        if(s==e)tree[node] = max(tree[node], d);
        else{
            ll mid = s+e>>1;
            upd(node<<1,s,mid,i,d); upd(node<<1|1,mid+1,e,i,d);
            tree[node] = max(tree[node<<1],tree[node<<1|1]);
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
} lseg[3], rseg[3], useg, dseg;
vector<pi> dp1[101010], dp2[101010];    //l,r
vector<pi> v[101010];
map<pi,ll> mp;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for(int i = 0 ; i < M ; i++){
        v[X[i]].push_back({Y[i], W[i]});
        mp[{X[i],Y[i]}] = W[i];
    }
    for(int i = 0 ; i < N ; i++){
        sort(all(v[i]));
        for(auto [j,_] : v[i])dp1[i].push_back({j,0});
        dp2[i] = dp1[i];
    }
    ll ans = 0;
    for(int i = 0 ; i < N ; i++){
        for(auto j : {1, 2}){
            if(i<j)break;
            for(int k = 0 ; k < dp1[i-j].size() ; k++){
                lseg[i-j].upd(1,0,N-1,dp1[i-j][k].first,dp1[i-j][k].second);
                rseg[i-j].upd(1,0,N-1,dp2[i-j][k].first,dp2[i-j][k].second);
            }
        }
        if(i>0)for(int j = (int)dp1[i].size()-1 ; j >= 0 ; j--){
            dp1[i][j].second = max({dp1[i][j].second, useg.query(1,0,N-1,dp1[i][j].first+1,N-1), rseg[1].tree[1]});
            dp1[i][j].second += mp[{i,dp1[i][j].first}];
            ans = max(ans, dp1[i][j].second);
            useg.upd(1,0,N-1,dp1[i][j].first,dp1[i][j].second);
        }
        if(i<N-1)for(int j = 0 ; j < dp2[i].size() ; j++){
            dp2[i][j].second = max({dp2[i][j].second, dseg.query(1,0,N-1,0,dp2[i][j].first-1), lseg[2].tree[1], rseg[2].tree[1]});
            dp2[i][j].second += mp[{i,dp2[i][j].first}];
            ans = max(ans, dp2[i][j].second);
            dseg.upd(1,0,N-1,dp2[i][j].first,dp2[i][j].second);
        }
    }
    return ans;
}

Compilation message

fish.cpp: In member function 'void segtree::upd(ll, ll, ll, ll, ll)':
fish.cpp:17:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |             ll mid = s+e>>1;
      |                      ~^~
fish.cpp: In member function 'll segtree::query(ll, ll, ll, ll, ll)':
fish.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         ll mid = s+e>>1;
      |                  ~^~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:47:31: 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]
   47 |             for(int k = 0 ; k < dp1[i-j].size() ; k++){
      |                             ~~^~~~~~~~~~~~~~~~~
fish.cpp:58:36: 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]
   58 |         if(i<N-1)for(int j = 0 ; j < dp2[i].size() ; j++){
      |                                  ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 45508 KB Output is correct
2 Correct 91 ms 47892 KB Output is correct
3 Correct 8 ms 32856 KB Output is correct
4 Correct 8 ms 32700 KB Output is correct
5 Runtime error 252 ms 153944 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 32860 KB Output is correct
2 Correct 165 ms 57564 KB Output is correct
3 Correct 221 ms 63024 KB Output is correct
4 Correct 75 ms 45504 KB Output is correct
5 Correct 94 ms 47940 KB Output is correct
6 Correct 7 ms 32860 KB Output is correct
7 Correct 7 ms 32860 KB Output is correct
8 Correct 7 ms 32860 KB Output is correct
9 Correct 7 ms 32676 KB Output is correct
10 Correct 8 ms 32896 KB Output is correct
11 Correct 8 ms 32856 KB Output is correct
12 Correct 89 ms 45508 KB Output is correct
13 Correct 124 ms 48068 KB Output is correct
14 Correct 87 ms 45240 KB Output is correct
15 Correct 91 ms 46528 KB Output is correct
16 Correct 82 ms 45240 KB Output is correct
17 Correct 91 ms 46436 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33112 KB Output is correct
2 Correct 8 ms 32760 KB Output is correct
3 Runtime error 55 ms 86668 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 32860 KB Output is correct
2 Runtime error 27 ms 66344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 32860 KB Output is correct
2 Runtime error 27 ms 66344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 32860 KB Output is correct
2 Runtime error 27 ms 66344 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 33112 KB Output is correct
2 Correct 8 ms 32760 KB Output is correct
3 Runtime error 55 ms 86668 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 45508 KB Output is correct
2 Correct 91 ms 47892 KB Output is correct
3 Correct 8 ms 32856 KB Output is correct
4 Correct 8 ms 32700 KB Output is correct
5 Runtime error 252 ms 153944 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -