oj.uz

Submission #682800

# Submission time Handle Problem Language Result Execution time Memory
682800 2023-01-17T03:41:58 Z sunwukong123 Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 154744 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define int long long 
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 100005;
map<int,int> dp[MAXN][2]; // dp[i][has this node been added by the left?][height]
map<pi,int> V;
int ans;
vector<int> H[MAXN];
vector<int> P[MAXN];
vector<pi> S[MAXN];
int S1, S3;
vector<pi> S2, S4;
 
int query1(int h) {
    return S1;
}
 
int query3(int h) {
    return S3;
}
 
int query2(int h){
    int res=prev(upper_bound(all(S2), pi(h,oo)))->s;
    return res;
}
int query4(int h) {
    reach
    int res=lower_bound(all(S4), pi(h,-oo))->s;
    reach
    return res;
}
long long max_weights(int32_t n, int32_t m, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W) {
    int height = 0;
    FOR(i,0,m-1){
        ++Y[i];
        V[pi(X[i],Y[i])]=W[i];
        chmax(height, (int)Y[i]);
        H[X[i]].pb(Y[i]);
        H[X[i]].pb(Y[i]-1);
    }
    FOR(i,0,n) {
        H[i].pb(0);
        H[i].pb(height);
        sort(all(H[i]));
        H[i].resize(unique(all(H[i])) - H[i].begin());

    }
 
    FOR(i,0,n){
        int t=0;
        for(auto curh:H[i]) {
            t+=V[pi(i,curh)];
            S[i].pb({curh,t});
        }

    }
    
    FOR(i,0,n-1) {


        
        if(i){
            for(auto h:H[i]) {
                
                chmax(dp[i][0][h], query1(h)); // chmax(dp[i][h][0], dp[i-1][y][1]);
                
                int s1=prev(upper_bound(all(S[i-1]), pi(h,oo)))->s;
                chmax(dp[i][0][h], s1 + query2(h)); //y<=h: chmax(dp[i][h][0], max{dp[i-1][y][0] - ss[i-1][y]} + ss[i-1][h]) 
                
                //chmax(dp[i][h][0], max(dp[i-1][y][0], dp[i-1][y][1]));
                chmax(dp[i][0][h], query3(h)); // chmax(dp[i][h][0], dp[i-1][y][0]);
                int s2=prev(upper_bound(all(S[i]), pi(h,oo)))->s;
                chmax(dp[i][1][h], query4(h) - s2); //y>h: chmax(dp[i][h][1], max(dp[i-1][y][0], dp[i-1][y][1]) + ss[i][y]-ss[i][h]);
                
                chmax(ans, dp[i][0][h]);
                chmax(ans, dp[i][1][h]);
                //chmax(dp[i][h][1], max(dp[i-1][y][0], dp[i-1][y][1]) + cc);
            }
        } 
        {
            
            S1=0;S3=0;
            for(auto y:H[i]) {
                chmax(S1, dp[i][1][y]);
                chmax(S3, dp[i][0][y]);
            }
            
            S2.clear(); S4.clear();
            S2.pb({0,0});
            for(auto y:H[i]) {
                db(y);
                db2(S[i][0].f,S[i][0].s);
                int sum = prev(upper_bound(all(S[i]),pi(y,oo)))->s;
                db(sum);
                int val=dp[i][0][y] - sum;
                if(val > S2.back().s) {
                    S2.pb({y, val});
                }
            }
            
 
            S4.pb({height, 0});
            for(auto it=H[i].rbegin(); it!=H[i].rend(); it++){ 
                int y=*it;
                int sum=prev(upper_bound(all(S[i+1]), pi(y,oo))) -> s;
                int val=max(dp[i][0][y], dp[i][1][y]) + sum;
                if(val > S4.back().s) {
                    S4.pb({y, val});
                }
            }
            reverse(all(S4));
        }
 

    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 78852 KB Output is correct
2 Correct 268 ms 86552 KB Output is correct
3 Correct 103 ms 62068 KB Output is correct
4 Correct 105 ms 62056 KB Output is correct
5 Execution timed out 1042 ms 142908 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 496 ms 100564 KB Output is correct
3 Correct 554 ms 110860 KB Output is correct
4 Correct 240 ms 79112 KB Output is correct
5 Correct 271 ms 86660 KB Output is correct
6 Correct 10 ms 16744 KB Output is correct
7 Correct 11 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 8 ms 16724 KB Output is correct
10 Correct 104 ms 62036 KB Output is correct
11 Correct 101 ms 62152 KB Output is correct
12 Correct 291 ms 80348 KB Output is correct
13 Correct 335 ms 88132 KB Output is correct
14 Correct 253 ms 79196 KB Output is correct
15 Correct 314 ms 86156 KB Output is correct
16 Correct 268 ms 79300 KB Output is correct
17 Correct 290 ms 85992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 62104 KB Output is correct
2 Correct 103 ms 62028 KB Output is correct
3 Correct 145 ms 60440 KB Output is correct
4 Correct 131 ms 63780 KB Output is correct
5 Correct 186 ms 69348 KB Output is correct
6 Correct 182 ms 69392 KB Output is correct
7 Correct 180 ms 69452 KB Output is correct
8 Correct 205 ms 69376 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16748 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16744 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 10 ms 16740 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 11 ms 16884 KB Output is correct
10 Correct 12 ms 17492 KB Output is correct
11 Correct 11 ms 17008 KB Output is correct
12 Correct 11 ms 17284 KB Output is correct
13 Correct 10 ms 16768 KB Output is correct
14 Correct 11 ms 17136 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16748 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16744 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 10 ms 16740 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 11 ms 16884 KB Output is correct
10 Correct 12 ms 17492 KB Output is correct
11 Correct 11 ms 17008 KB Output is correct
12 Correct 11 ms 17284 KB Output is correct
13 Correct 10 ms 16768 KB Output is correct
14 Correct 11 ms 17136 KB Output is correct
15 Correct 10 ms 16980 KB Output is correct
16 Correct 12 ms 17392 KB Output is correct
17 Correct 86 ms 30824 KB Output is correct
18 Correct 76 ms 30192 KB Output is correct
19 Correct 70 ms 29112 KB Output is correct
20 Correct 68 ms 29160 KB Output is correct
21 Correct 68 ms 29056 KB Output is correct
22 Correct 167 ms 41036 KB Output is correct
23 Correct 27 ms 20952 KB Output is correct
24 Correct 65 ms 29076 KB Output is correct
25 Correct 11 ms 17284 KB Output is correct
26 Correct 26 ms 20376 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16748 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16744 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 10 ms 16740 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Correct 11 ms 16884 KB Output is correct
10 Correct 12 ms 17492 KB Output is correct
11 Correct 11 ms 17008 KB Output is correct
12 Correct 11 ms 17284 KB Output is correct
13 Correct 10 ms 16768 KB Output is correct
14 Correct 11 ms 17136 KB Output is correct
15 Correct 10 ms 16980 KB Output is correct
16 Correct 12 ms 17392 KB Output is correct
17 Correct 86 ms 30824 KB Output is correct
18 Correct 76 ms 30192 KB Output is correct
19 Correct 70 ms 29112 KB Output is correct
20 Correct 68 ms 29160 KB Output is correct
21 Correct 68 ms 29056 KB Output is correct
22 Correct 167 ms 41036 KB Output is correct
23 Correct 27 ms 20952 KB Output is correct
24 Correct 65 ms 29076 KB Output is correct
25 Correct 11 ms 17284 KB Output is correct
26 Correct 26 ms 20376 KB Output is correct
27 Correct 17 ms 19540 KB Output is correct
28 Correct 433 ms 81528 KB Output is correct
29 Correct 693 ms 105040 KB Output is correct
30 Correct 752 ms 152560 KB Output is correct
31 Correct 764 ms 152640 KB Output is correct
32 Correct 543 ms 94796 KB Output is correct
33 Correct 760 ms 154492 KB Output is correct
34 Correct 778 ms 154744 KB Output is correct
35 Correct 249 ms 65436 KB Output is correct
36 Correct 794 ms 144124 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 62104 KB Output is correct
2 Correct 103 ms 62028 KB Output is correct
3 Correct 145 ms 60440 KB Output is correct
4 Correct 131 ms 63780 KB Output is correct
5 Correct 186 ms 69348 KB Output is correct
6 Correct 182 ms 69392 KB Output is correct
7 Correct 180 ms 69452 KB Output is correct
8 Correct 205 ms 69376 KB Output is correct
9 Correct 324 ms 110192 KB Output is correct
10 Correct 161 ms 58476 KB Output is correct
11 Correct 360 ms 99920 KB Output is correct
12 Correct 10 ms 16724 KB Output is correct
13 Correct 10 ms 16724 KB Output is correct
14 Correct 9 ms 16648 KB Output is correct
15 Correct 8 ms 16748 KB Output is correct
16 Correct 9 ms 16708 KB Output is correct
17 Correct 8 ms 16724 KB Output is correct
18 Correct 101 ms 62248 KB Output is correct
19 Correct 101 ms 62072 KB Output is correct
20 Correct 113 ms 62016 KB Output is correct
21 Correct 115 ms 62112 KB Output is correct
22 Correct 317 ms 108588 KB Output is correct
23 Correct 474 ms 140632 KB Output is correct
24 Correct 473 ms 143840 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 78852 KB Output is correct
2 Correct 268 ms 86552 KB Output is correct
3 Correct 103 ms 62068 KB Output is correct
4 Correct 105 ms 62056 KB Output is correct
5 Execution timed out 1042 ms 142908 KB Time limit exceeded
6 Halted 0 ms 0 KB -