Submission #720535

#	Time	Username	Problem	Language	Result	Execution time	Memory
720535		lam	Catfish Farm (IOI22_fish)	C++17	3 / 100	97 ms	8104 KiB

fish

#include "fish.h"

#include <vector>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 3e5 + 10;
int n,m;
ii a[maxn]; int w[maxn];
ll sub2(vector <int> X, vector <int> Y, vector <int> W)
{
    ll ans=0;
    ll sum=0;
    for (int i=0; i<m; i++)
        if (X[i]==0) sum+=W[i];
    ans=sum;
    sum=0;
    for (int i=0; i<m; i++)
        if (X[i]==1) sum+=W[i];
    ans=max(ans,sum);
    return ans;
}

ll sub1(const vector <int> &W)
{
    ll sum=0LL;
    for (int i:W) sum+=i;
    return sum;
}

bool cmp(int x, int y)
{
    return a[x]<a[y];
}

ll sub3()
{
    vector <int> id;
    for (int i=0; i<m; i++) id.push_back(i);
    sort(id.begin(),id.end(),cmp);
    vector <int> b(n,0);
    for (int i=0; i<m; i++)
        b[a[i].ff] += w[i];
    vector <int> dp[3];
    for (int i=0; i<3; i++) dp[i].assign(n,0);
    dp[1][0] = b[0];
    for (int i=0; i+1<n; i++)
    {
        for (int j=0; j<3; j++)
        {
            if (j==1) dp[i+1][2] = max(dp[i+1][2],dp[i][j]+b[i+1]);
            else dp[i+1][0] = max(dp[i+1][0],dp[i][j]);
            int val=0;
            if (j==0) val+=b[i];
            dp[i+1][1] = max(dp[i+1][1],dp[i][j]+val);
        }
    }
    int ans=max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
    return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n=N; m=M;
    bool check_sub=1;
    for (int i:X) if (i%2==1) check_sub=0;
    if (check_sub) return sub1(W);
    check_sub=1;
    for (int i:X) if (i>1) check_sub=0;
    if (check_sub) return sub2(X,Y,W);
    check_sub=1;
    for (int i:Y) if (i!=0) check_sub=0;
    for (int i=0; i<m; i++) a[i]={X[i],Y[i]}, w[i]=W[i];
    if (check_sub) sub3();
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 0 / 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