oj.uz

Submission #966209

# Submission time Handle Problem Language Result Execution time Memory
966209 2024-04-19T14:14:58 Z andrej246 Catfish Farm (IOI22_fish) C++17
6 / 100
 69 ms 8784 KB 
#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

#define NL '\n'
#define EL cout << NL
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define FORS(i,s,n) for(int i = (s); i < (n); i++)
#define PRINTV(v) for(auto a:v) {cout << a << " ";} EL;
#define PRINTVV(v) for(auto a:v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()
#define STRP(p) "{" << (p).f << "," << (p).s << "}"
#define PRINTVP(v) for(auto a:v) {cout << STRP(a) << " ";} EL;
#define PRINTVVP(v) for(auto a:v) {PRINTVP(a);}

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    bool even = true;
    bool smallx = true;
    bool smally =  true;
    FOR(i,M) {
        if (X[i] % 2 == 1) even = false;
        if (X[i] <= 1) smallx = false;
        if (Y[i] != 0) smally = false;
    }
    even = false;
    if (even) {
        ll res = 0;
        FOR(i,M) {
            res += W[i];
        }
        return res;
    }
    smallx = true;
    if (smallx) {
        vl left(N);
        vl right(N);
        FOR(i,M) {
            if (X[i] == 0) left[Y[i]] = W[i];
            else right[Y[i]] = W[i];
        }
        if (N == 2) {
            return max(right[0]+right[1],left[0]+left[1]);
        }
        ll ans = 0;
        FOR(i,N) {
            ans += right[i];
        }
        ll psum = ans;
        FOR(i,N) {
            psum += left[i]-right[i];
            ans = max(ans,psum);
        }
        return ans;
    }
    if (smally) {
        vector<array<array<ll,2>,2>> dp(N);
        vl a(N);
        FOR(i,M) a[X[i]] = W[i];
        dp[0][0] = {0,0};
        dp[0][1] = {0,0};
        FORS(i,1,N) {
            dp[i][0][0] = max(dp[i-1][0][0],dp[i-1][1][0]);
            dp[i][1][0] = max(dp[i-1][0][1],dp[i-1][1][1]) + a[i];
            dp[i][0][1] = max(dp[i-1][1][0],dp[i-1][0][0] + a[i-1]);
            dp[i][1][1] = max(dp[i-1][0][1],dp[i-1][1][1]);
        }
        return max(dp[N-1][0][0],max(dp[N-1][0][1],max(dp[N-1][1][0],dp[N-1][1][1])));
    }
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3672 KB Output is correct
2 Correct 23 ms 4188 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Incorrect 69 ms 8784 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '49851995244248'
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 37 ms 5404 KB Output is correct
3 Correct 45 ms 6636 KB Output is correct
4 Correct 19 ms 3696 KB Output is correct
5 Correct 24 ms 4180 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 1 ms 1880 KB Output is correct
12 Correct 19 ms 3668 KB Output is correct
13 Correct 24 ms 4176 KB Output is correct
14 Correct 19 ms 3676 KB Output is correct
15 Correct 21 ms 4060 KB Output is correct
16 Correct 19 ms 3676 KB Output is correct
17 Correct 22 ms 4052 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 2020 KB Output is correct
3 Incorrect 13 ms 2908 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '774766749'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2268305442'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2268305442'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 348 KB Output is correct
9 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '2268305442'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 2020 KB Output is correct
3 Incorrect 13 ms 2908 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '774766749'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3672 KB Output is correct
2 Correct 23 ms 4188 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 1884 KB Output is correct
5 Incorrect 69 ms 8784 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '49851995244248'
6 Halted 0 ms 0 KB -