oj.uz

Submission #1049797

# Submission time Handle Problem Language Result Execution time Memory
1049797 2024-08-09T05:14:19 Z wXs Catfish Farm (IOI22_fish) C++17
6 / 100
 240 ms 147516 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,-1e18});
        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, lseg[2].tree[1], rseg[2].tree[1], useg.query(1,0,N-1,dp1[i][j].first+1,N-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, rseg[1].tree[1], dseg.query(1,0,N-1,0,dp2[i][j].first-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 75 ms 43972 KB Output is correct
2 Correct 90 ms 46232 KB Output is correct
3 Correct 8 ms 32856 KB Output is correct
4 Correct 8 ms 32728 KB Output is correct
5 Runtime error 240 ms 147516 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 167 ms 54896 KB Output is correct
3 Correct 212 ms 59440 KB Output is correct
4 Correct 73 ms 43972 KB Output is correct
5 Correct 105 ms 46148 KB Output is correct
6 Correct 8 ms 32860 KB Output is correct
7 Correct 7 ms 32896 KB Output is correct
8 Correct 7 ms 32860 KB Output is correct
9 Correct 7 ms 32776 KB Output is correct
10 Correct 7 ms 32860 KB Output is correct
11 Correct 7 ms 32756 KB Output is correct
12 Correct 90 ms 43968 KB Output is correct
13 Correct 111 ms 46144 KB Output is correct
14 Correct 88 ms 43820 KB Output is correct
15 Correct 92 ms 44964 KB Output is correct
16 Correct 81 ms 43940 KB Output is correct
17 Correct 93 ms 44976 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 32856 KB Output is correct
2 Correct 8 ms 32860 KB Output is correct
3 Runtime error 55 ms 85752 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 7 ms 32860 KB Output is correct
2 Runtime error 25 ms 66308 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 7 ms 32860 KB Output is correct
2 Runtime error 25 ms 66308 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 7 ms 32860 KB Output is correct
2 Runtime error 25 ms 66308 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 8 ms 32856 KB Output is correct
2 Correct 8 ms 32860 KB Output is correct
3 Runtime error 55 ms 85752 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 75 ms 43972 KB Output is correct
2 Correct 90 ms 46232 KB Output is correct
3 Correct 8 ms 32856 KB Output is correct
4 Correct 8 ms 32728 KB Output is correct
5 Runtime error 240 ms 147516 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -