Submission #674363

#	Time	Username	Problem	Language	Result	Execution time	Memory
674363		__Davit__	Catfish Farm (IOI22_fish)	C++17	9 / 100	80 ms	14028 KiB

fish

#pragma once

#include <bits/stdc++.h>


#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define Davit cout.tie(NULL);

using namespace std;
const ll mod = 1e9 + 7;
const int INF = 1e9;

using namespace std;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    bool isok = 1;
    bool isok2 = 1;
    bool isok3 = 1;
    for (int i = 0; i < M; i++) {
        if (X[i] & 1)isok = 0;
        if (X[i] > 1)isok2 = 0;
        if (Y[i] >= 1)isok3 = 0;
    }
    if (isok) return accumulate(W.begin(), W.end(), 0ll);
    if (isok2) {
        ll res = 0;
        vector<ll> p1(N), p2(N);
        for (int i = 0; i < M; ++i) {
            if (X[i] == 0)p1[Y[i]] = W[i];
            if (X[i] == 1)p2[Y[i]] = W[i];
        }
        for (int i = 1; i < N; i++) {
            p1[i] += p1[i - 1];
            p2[i] += p2[i - 1];
        }
        res = max(p1[N - 1], p2[N - 1]);
        if (N > 2) {
            for (int i = 0; i < N; i++) res = max(res, p2[N - 1] + p1[i] - p2[i]);
        }
        return res;
    }
    if (isok3) {
        vector<ll> dp(N, 0);
        dp[0] = 0;
        dp[1] = max(W[0], W[1]);
        vector<ll> v(N);
        for (int i = 0; i < M; i++) v[X[i]] = W[i];
        for (int i = 2; i < N; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2]);
            dp[i] = max(dp[i], dp[i - 2] + max(v[i], v[i - 1]));
            if (i - 3 >= 0) {
                dp[i] = max(dp[i], dp[i - 3] + v[i] + v[i - 2]);
            } else dp[i] = max(dp[i], v[i] + v[i - 2]);
        }
        for (int i = 0; i < N; i++)cout << dp[i] << " ";
        return dp[N - 1];
    }

}
//10 9
//0 0 1
//1 0 1
//2 0 1
//3 0 1
//4 0 10
//5 0 1
//6 0 1
//7 0 1
//8 0 1

Compilation message (stderr)

fish.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16