oj.uz

Submission #1090205

# Submission time Handle Problem Language Result Execution time Memory
1090205 2024-09-18T01:31:19 Z steveonalex Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 KB 
#include <bits/stdc++.h>
#include "fish.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
double rngesus_d(double l, double r){
    double cur = rngesus(0, MASK(60) - 1);
    cur /= MASK(60) - 1;
    return l + cur * (r - l);
}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const ll INF = 1e18 + 69;

int n, m;
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]++;
    }

    ll grid[n + 2][n + 2];
    memset(grid, 0, sizeof grid);
    for(int i = 0; i<m; ++i){
        grid[X[i]][Y[i]] = W[i];
    }

    for(int i = 1; i<=n; ++i){
        for(int j = 1; j<=n; ++j) grid[i][j] += grid[i][j-1];
    }

    ll dp[n+2][n+2][2];
    // dp[n][m][ascending];
    for(int i = 0; i<=n+1; ++i) for(int j = 0; j<=n+1; ++j) for(int x = 0; x <= 1; ++x)
        dp[i][j][x] = -INF;
    dp[0][0][1] = 0;
    for(int i = 1; i<=n; ++i){
        maximize(dp[i][0][1], dp[i-1][0][0]);
        // increase
        block_of_code{
            ll pref[n + 2]; fill(pref, pref + n + 2, -INF);
            for(int j = 0; j <= n; ++j) pref[j] = dp[i-1][j][1] - grid[i-1][j];

            for(int j = 0; j <= n; ++j){
                if (j > 0) maximize(pref[j], pref[j-1]);
                maximize(dp[i][j][1], pref[j] + grid[i-1][j]);
            }
        }

        // decrease
        block_of_code{
            ll suff[n+2]; fill(suff, suff + n + 2, -INF);
            for(int j = 0; j <= n; ++j) suff[j] = max(dp[i-1][j][0], dp[i-1][j][1]) + grid[i][j];

            for(int j = n; j >= 0; --j){
                if (j < n) maximize(suff[j], suff[j+1]);
                maximize(dp[i][j][0], suff[j] - grid[i][j]);
            }
        }


        // jump two
        if (i >= 2){
            for(int j = 1; j <= n; ++j) for(int x = 0; x <= 1; ++x){
                for(int k = 1; k <= n; ++k){
                    ll sum = grid[i-1][max(j,k)];
                    maximize(dp[i][k][1], dp[i-2][j][x] + sum);
                }
            }
        }
    }


    ll ans = 0;
    for(int j = 0; j <= n; ++j) for(int x = 0; x <= 1; ++x) maximize(ans, dp[n][j][x]);
    return ans;
}


// int main(void){
//     ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
//     clock_t start = clock();

//     int n, m; cin >> n >> m;
//     vector<int> X(m), Y(m), W(m);
//     for(int i = 0; i<m; ++i){
//         cin >> X[i] >> Y[i] >> W[i];
//     }

//     cout << max_weights(n, m, X, Y, W) << "\n";


//     cerr << "Time elapsed: " << clock() - start << " ms\n";
//     return 0;
// }

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 945 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 948 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 966 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 65 ms 2648 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 57 ms 2396 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 56 ms 2396 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 65 ms 2648 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 57 ms 2396 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 56 ms 2396 KB Output is correct
15 Correct 57 ms 2392 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 80 ms 4412 KB Output is correct
18 Correct 64 ms 4296 KB Output is correct
19 Correct 64 ms 4188 KB Output is correct
20 Correct 64 ms 4188 KB Output is correct
21 Correct 64 ms 4188 KB Output is correct
22 Correct 72 ms 5968 KB Output is correct
23 Correct 59 ms 2904 KB Output is correct
24 Correct 62 ms 3672 KB Output is correct
25 Correct 56 ms 2396 KB Output is correct
26 Correct 58 ms 3160 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 65 ms 2648 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 57 ms 2396 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 56 ms 2396 KB Output is correct
15 Correct 57 ms 2392 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 80 ms 4412 KB Output is correct
18 Correct 64 ms 4296 KB Output is correct
19 Correct 64 ms 4188 KB Output is correct
20 Correct 64 ms 4188 KB Output is correct
21 Correct 64 ms 4188 KB Output is correct
22 Correct 72 ms 5968 KB Output is correct
23 Correct 59 ms 2904 KB Output is correct
24 Correct 62 ms 3672 KB Output is correct
25 Correct 56 ms 2396 KB Output is correct
26 Correct 58 ms 3160 KB Output is correct
27 Execution timed out 1083 ms 211956 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 966 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 945 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -