oj.uz

Submission #635500

# Submission time Handle Problem Language Result Execution time Memory
635500 2022-08-26T10:45:55 Z OttoTheDino Catfish Farm (IOI22_fish) C++17
9 / 100
 750 ms 133236 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,s,e)              for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)             for (ll i = s; i >= e; --i)
#define len(v)                  (ll)v.size()
#define pb                      push_back
#define all(v)                  v.begin(), v.end()
#define fi                      first
#define se                      second
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef pair<ll,ll> pll;
 
ll max_weights(int n, int m, vi X, vi Y, vi W) {
    bool done[n+5] = {};
    vector<ll> check[n+5], fish[n+5];
    unordered_map<ll,ll> w[n+5], dp[n+5][2];
 
    rep (i,0,m-1) {
        fish[X[i]+1].pb(Y[i]+1);
        w[X[i]+1][Y[i]+1] = W[i];
        check[X[i]+1].pb(Y[i]);
        if (Y[i]==0) done[X[i]+1] = 1;
    }
 
    rep (i,0,n) {
        if (i) check[i].pb(n);
        if (!done[i]) check[i].pb(0);
    }
 
    rep (i,1,n) {
 
        {
            //go bigger
            vector<pll> upd;
            set<ll> st;
            for (ll el : check[i]) upd.pb({el,1});
            for (ll el : fish[i-1]) upd.pb({el,0});
            for (ll el : check[i-1]) upd.pb({el,2});
            sort (all(upd));
            ll sum = 0;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) {
                    sum += w[i-1][y]; 
                }
                if (tp==1) {
                    ll res;
                    if (len(st)) {
                        res = sum+*st.rbegin();
                    }
                    else res = 0;
                    dp[i][0][y] = max(dp[i][0][y], res);
                    //cout << "1: " << i << " " << y << " " << dp[i][0][y] << endl;
                }
                if (tp==2) {
                    st.insert(dp[i-1][0][y]-sum);
                }
            }
        }
 
        {
            //go smaller
            vector<pll> upd;
            ll sum = 0, cur = 0;
            for (ll el : check[i]) upd.pb({el,3});
            for (ll el : fish[i+1]) {
                upd.pb({el, 0});
                sum += w[i+1][el]; 
            }
            for (ll el : fish[i]) {
                upd.pb({el, 1});
                cur += w[i][el];
            }
            for (ll el : check[i-1]) upd.pb ({el, 2});
            sort (all(upd));
            reverse(all(upd));
            set<ll> st;
            for (pll el : upd) {
                ll y = el.fi, tp = el.se;
                if (tp==0) sum -= w[i+1][y]; 
                if (tp==1) cur -= w[i][y];
                if (tp==2) st.insert({dp[i-1][1][y]});
                if (tp==3) {
                    ll res = dp[i-1][0][n]+cur;
                    if (len(st)) res = max(res, *st.rbegin());
                    if (y==n) res = max(res, dp[i][0][n]+cur);
                    dp[i][1][y] = res-cur+sum;
                    //cout << "2: " << i << " " << y << " " << dp[i][1][y] << endl;
                    dp[i+1][0][y] = dp[i][1][y];
                }
            }
        }
    }
 
    ll ans = 0;
    for (ll y : check[n]) {
        ans = max(ans, dp[n][0][y]);
        ans = max(ans, dp[n][1][y]);
    }
 
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 69956 KB Output is correct
2 Correct 268 ms 81988 KB Output is correct
3 Correct 107 ms 58956 KB Output is correct
4 Correct 106 ms 58956 KB Output is correct
5 Correct 750 ms 133236 KB Output is correct
6 Correct 690 ms 117988 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 430 ms 85368 KB Output is correct
3 Correct 527 ms 101060 KB Output is correct
4 Correct 230 ms 69776 KB Output is correct
5 Correct 271 ms 81652 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 112 ms 59012 KB Output is correct
11 Correct 107 ms 58964 KB Output is correct
12 Correct 243 ms 69708 KB Output is correct
13 Correct 303 ms 81620 KB Output is correct
14 Correct 231 ms 69732 KB Output is correct
15 Correct 272 ms 78528 KB Output is correct
16 Correct 229 ms 69640 KB Output is correct
17 Correct 267 ms 79700 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 59044 KB Output is correct
2 Correct 111 ms 59060 KB Output is correct
3 Incorrect 173 ms 64176 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 468 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '310323004046'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 59044 KB Output is correct
2 Correct 111 ms 59060 KB Output is correct
3 Incorrect 173 ms 64176 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 69956 KB Output is correct
2 Correct 268 ms 81988 KB Output is correct
3 Correct 107 ms 58956 KB Output is correct
4 Correct 106 ms 58956 KB Output is correct
5 Correct 750 ms 133236 KB Output is correct
6 Correct 690 ms 117988 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 430 ms 85368 KB Output is correct
9 Correct 527 ms 101060 KB Output is correct
10 Correct 230 ms 69776 KB Output is correct
11 Correct 271 ms 81652 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 112 ms 59012 KB Output is correct
17 Correct 107 ms 58964 KB Output is correct
18 Correct 243 ms 69708 KB Output is correct
19 Correct 303 ms 81620 KB Output is correct
20 Correct 231 ms 69732 KB Output is correct
21 Correct 272 ms 78528 KB Output is correct
22 Correct 229 ms 69640 KB Output is correct
23 Correct 267 ms 79700 KB Output is correct
24 Correct 117 ms 59044 KB Output is correct
25 Correct 111 ms 59060 KB Output is correct
26 Incorrect 173 ms 64176 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
27 Halted 0 ms 0 KB -