oj.uz

Submission #829277

# Submission time Handle Problem Language Result Execution time Memory
829277 2023-08-18T08:01:41 Z otarius Catfish Farm (IOI22_fish) C++17
3 / 100
 341 ms 42872 KB 
#include "fish.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long
 
// #define int long long
// #define int unsigned long long
 
const ll inf = 1e18 + 7;
const ll weirdMod = 998244353;
 
int n, m, y, w;
struct segtree {
    ll t[400040];
    void init() {
        for (int i = 1; i <= 400000; i++) t[i] = -inf;
    }
    
    void update(int v, int tl, int tr, int pos, ll val) {
        if (tl == tr) {
            t[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(2 * v, tl, tm, pos, val);
        else update(2 * v + 1, tm + 1, tr, pos, val);
        t[v] = max(t[2 * v], t[2 * v + 1]);
    }
    
    ll getmax(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return -inf;
        if (tl == l && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        return max(getmax(2 * v, tl, tm, l, min(r, tm)),
                   getmax(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
    }
} t1, t2;
 
vector<pll> pos[100005];
vector<ll> dp1[100005];
vector<ll> dp2[100005];
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N; m = M;
    
    for (int i = 0; i < M; i++) {
        X[i]++; Y[i]++;
        pos[X[i]].pb({Y[i], W[i]});
    }
    for (int i = 0; i <= n + 1; i++) {
        sort(pos[i].begin(), pos[i].end());
        if (pos[i].empty() || pos[i][0].ff != 1) pos[i].pb({1, 0});
        sort(pos[i].begin(), pos[i].end());
        if (pos[i].back().ff != n) pos[i].pb({n, 0});
        
        dp1[i] = vector<ll>(pos[i].size(), -inf);
        dp2[i] = vector<ll>(pos[i].size(), -inf);
    }
    
    t1.init(); t2.init();
    
    dp1[0][dp1[0].size() - 1] = 0; dp2[0][0] = 0;
    ll a = -inf, b = -inf, ans = 0;
    for (int i = 0; i <= n + 1; i++) {
        int k = pos[i].size();
        
        if (i >= 1) a = max(a, dp2[i - 1][0]);
        if (i >= 2) b = max(b, dp1[i - 2].back());
        
        dp1[i][0] = max(dp1[i][0], a + pos[i][0].sc);
        if (i >= 2) dp1[i][0] = max(dp1[i][0], dp1[i - 2].back() + pos[i][0].sc);
        dp2[i][k - 1] = max(dp2[i][k - 1], b + pos[i][k - 1].sc);
        
        for (int j = 0; j < k; j++) {
            y = pos[i][j].ff;
            w = pos[i][j].sc;
            
            dp1[i][j] = max(dp1[i][j], t1.getmax(1, 1, n, 1, y - 1) + w);
            t1.update(1, 1, n, y, dp1[i][j]);
        }
        
        for (int j = k - 1; j >= 0; j--) {
            y = pos[i][j].ff;
            w = pos[i][j].sc;
            
            dp2[i][j] = max(dp2[i][j], t2.getmax(1, 1, n, y, n) + w);
            t2.update(1, 1, n, y, dp2[i][j]);
        }
        
        ans = max(ans, dp2[i][0]);
    }
    
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 27836 KB Output is correct
2 Correct 121 ms 30024 KB Output is correct
3 Correct 66 ms 24544 KB Output is correct
4 Correct 57 ms 24548 KB Output is correct
5 Correct 255 ms 40996 KB Output is correct
6 Correct 341 ms 42872 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13524 KB Output is correct
2 Incorrect 161 ms 32364 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40603598155790'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 24552 KB Output is correct
2 Correct 57 ms 24568 KB Output is correct
3 Incorrect 75 ms 24780 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 24552 KB Output is correct
2 Correct 57 ms 24568 KB Output is correct
3 Incorrect 75 ms 24780 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 27836 KB Output is correct
2 Correct 121 ms 30024 KB Output is correct
3 Correct 66 ms 24544 KB Output is correct
4 Correct 57 ms 24548 KB Output is correct
5 Correct 255 ms 40996 KB Output is correct
6 Correct 341 ms 42872 KB Output is correct
7 Correct 6 ms 13524 KB Output is correct
8 Incorrect 161 ms 32364 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40603598155790'
9 Halted 0 ms 0 KB -