oj.uz

Submission #682805

# Submission time Handle Problem Language Result Execution time Memory
682805 2023-01-17T03:51:52 Z sunwukong123 Catfish Farm (IOI22_fish) C++17
81 / 100
 1000 ms 148044 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;
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native")
 
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;
        S[i].pb({0,0});
        for(auto curh:H[i]) {
            t+=V[pi(i,curh)];

            if(S[i].back().s != t)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 232 ms 77308 KB Output is correct
2 Correct 294 ms 84744 KB Output is correct
3 Correct 99 ms 60492 KB Output is correct
4 Correct 102 ms 60548 KB Output is correct
5 Execution timed out 1020 ms 140408 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16696 KB Output is correct
2 Correct 466 ms 98532 KB Output is correct
3 Correct 582 ms 109024 KB Output is correct
4 Correct 235 ms 77328 KB Output is correct
5 Correct 280 ms 84764 KB Output is correct
6 Correct 10 ms 16724 KB Output is correct
7 Correct 11 ms 16744 KB Output is correct
8 Correct 8 ms 16724 KB Output is correct
9 Correct 8 ms 16704 KB Output is correct
10 Correct 99 ms 60560 KB Output is correct
11 Correct 106 ms 60620 KB Output is correct
12 Correct 307 ms 78684 KB Output is correct
13 Correct 359 ms 86372 KB Output is correct
14 Correct 267 ms 77356 KB Output is correct
15 Correct 307 ms 84144 KB Output is correct
16 Correct 252 ms 77520 KB Output is correct
17 Correct 290 ms 84016 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 60584 KB Output is correct
2 Correct 104 ms 60548 KB Output is correct
3 Correct 139 ms 59024 KB Output is correct
4 Correct 133 ms 62428 KB Output is correct
5 Correct 182 ms 69064 KB Output is correct
6 Correct 176 ms 69120 KB Output is correct
7 Correct 231 ms 69256 KB Output is correct
8 Correct 201 ms 69072 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16744 KB Output is correct
7 Correct 9 ms 16748 KB Output is correct
8 Correct 8 ms 16740 KB Output is correct
9 Correct 9 ms 16852 KB Output is correct
10 Correct 11 ms 17360 KB Output is correct
11 Correct 9 ms 17028 KB Output is correct
12 Correct 10 ms 17264 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17108 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16744 KB Output is correct
7 Correct 9 ms 16748 KB Output is correct
8 Correct 8 ms 16740 KB Output is correct
9 Correct 9 ms 16852 KB Output is correct
10 Correct 11 ms 17360 KB Output is correct
11 Correct 9 ms 17028 KB Output is correct
12 Correct 10 ms 17264 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17108 KB Output is correct
15 Correct 11 ms 16980 KB Output is correct
16 Correct 14 ms 17292 KB Output is correct
17 Correct 80 ms 29680 KB Output is correct
18 Correct 74 ms 29796 KB Output is correct
19 Correct 83 ms 28880 KB Output is correct
20 Correct 69 ms 28788 KB Output is correct
21 Correct 68 ms 28748 KB Output is correct
22 Correct 135 ms 40608 KB Output is correct
23 Correct 25 ms 20660 KB Output is correct
24 Correct 67 ms 28072 KB Output is correct
25 Correct 10 ms 17240 KB Output is correct
26 Correct 23 ms 20180 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16716 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16724 KB Output is correct
6 Correct 9 ms 16744 KB Output is correct
7 Correct 9 ms 16748 KB Output is correct
8 Correct 8 ms 16740 KB Output is correct
9 Correct 9 ms 16852 KB Output is correct
10 Correct 11 ms 17360 KB Output is correct
11 Correct 9 ms 17028 KB Output is correct
12 Correct 10 ms 17264 KB Output is correct
13 Correct 9 ms 16724 KB Output is correct
14 Correct 10 ms 17108 KB Output is correct
15 Correct 11 ms 16980 KB Output is correct
16 Correct 14 ms 17292 KB Output is correct
17 Correct 80 ms 29680 KB Output is correct
18 Correct 74 ms 29796 KB Output is correct
19 Correct 83 ms 28880 KB Output is correct
20 Correct 69 ms 28788 KB Output is correct
21 Correct 68 ms 28748 KB Output is correct
22 Correct 135 ms 40608 KB Output is correct
23 Correct 25 ms 20660 KB Output is correct
24 Correct 67 ms 28072 KB Output is correct
25 Correct 10 ms 17240 KB Output is correct
26 Correct 23 ms 20180 KB Output is correct
27 Correct 16 ms 19324 KB Output is correct
28 Correct 456 ms 80592 KB Output is correct
29 Correct 683 ms 103648 KB Output is correct
30 Correct 751 ms 146164 KB Output is correct
31 Correct 729 ms 146212 KB Output is correct
32 Correct 562 ms 94404 KB Output is correct
33 Correct 737 ms 148008 KB Output is correct
34 Correct 755 ms 148044 KB Output is correct
35 Correct 230 ms 63180 KB Output is correct
36 Correct 772 ms 141464 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 60584 KB Output is correct
2 Correct 104 ms 60548 KB Output is correct
3 Correct 139 ms 59024 KB Output is correct
4 Correct 133 ms 62428 KB Output is correct
5 Correct 182 ms 69064 KB Output is correct
6 Correct 176 ms 69120 KB Output is correct
7 Correct 231 ms 69256 KB Output is correct
8 Correct 201 ms 69072 KB Output is correct
9 Correct 357 ms 106736 KB Output is correct
10 Correct 179 ms 58236 KB Output is correct
11 Correct 393 ms 99660 KB Output is correct
12 Correct 9 ms 16724 KB Output is correct
13 Correct 10 ms 16724 KB Output is correct
14 Correct 8 ms 16724 KB Output is correct
15 Correct 12 ms 16628 KB Output is correct
16 Correct 8 ms 16668 KB Output is correct
17 Correct 8 ms 16724 KB Output is correct
18 Correct 109 ms 60564 KB Output is correct
19 Correct 105 ms 60460 KB Output is correct
20 Correct 121 ms 60656 KB Output is correct
21 Correct 103 ms 60444 KB Output is correct
22 Correct 330 ms 104656 KB Output is correct
23 Correct 545 ms 135408 KB Output is correct
24 Correct 522 ms 137792 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 77308 KB Output is correct
2 Correct 294 ms 84744 KB Output is correct
3 Correct 99 ms 60492 KB Output is correct
4 Correct 102 ms 60548 KB Output is correct
5 Execution timed out 1020 ms 140408 KB Time limit exceeded
6 Halted 0 ms 0 KB -