Submission #774224

#	Time	Username	Problem	Language	Result	Execution time	Memory
774224		jasmin	Catfish Farm (IOI22_fish)	C++17	9 / 100	76 ms	10852 KiB

fish

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

#define ll long long


long long subtask1(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W){

    long long ans=0;
    for(int i=0; i<M; i++){
        ans+=W[i];
    }
    return ans;
}
long long subtask2(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W){
    
    vector<pair<int,int>> c0;
    vector<pair<int,int>> c1;
    long long sum0=0;
    long long sum1=0;
    for(int i=0; i<M; i++){

        if(X[i]==0){
            c0.push_back({Y[i], W[i]});
            sum0+=W[i];
        }
        else{
            c1.push_back({Y[i], W[i]});
            sum1+=W[i];
        }

    }
    
    if(N==2){
        return max(sum0, sum1);
    }

    sort(c1.begin(), c1.end());
    sort(c0.begin(), c0.end());
    long long ans=max(sum0, sum1);
    long long mom=sum1;
    int j=0;
    for(int i=0; i<(int)c1.size(); i++){

        while(j<(int)c0.size() && c0[j].first<c1[i].first){

            mom+=c0[j].second;
            j++;

        }

        ans=max(ans, mom);

        mom-=c1[i].second;
    }
    return ans;
}

long long gain(int h1, int free1, int h2, int free2, vector<pair<int,int> >& c1, vector<pair<int,int> >& c2){

    //wand von 1 ist grösser

    int wallh=c1[h1].first;

    ll ans=0;
    for(int i=max(h2, (int)c2.size()-free2); i<(int)c2.size(); i++){
        
        if(c2[i].first < wallh){
            ans+= c2[i].second;
        }
    }
    return ans;

}

const int INF=1e9+7;
long long subtask3(int n, int m, vector<int> x, vector<int> y, vector<int> w){

    vector<int> weight(n);
    for(int i=0; i<m; i++){
        weight[x[i]]=w[i];
    }

    vector<vector<long long> > dp(n, vector<long long> (2, 0)); //0: free, 1: wall
    for(int i=1; i<n; i++){

        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + w[i]);

        dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
        if(0<=i-2){
            dp[i][1] = max(dp[i][1], max(dp[i-2][0], dp[i-2][1]) + w[i-1]);
        }
    }

    return max(dp[n-1][0], dp[n-1][1]);

}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

    if(N==1) return 0;

    bool sub1=true;
    bool sub2=true;
    bool sub3=true;
    for(int i=0; i<M; i++){

        if(X[i]%2==1){
            sub1=false;
        }
        if(X[i]>1){
            sub2=false;
        }
        if(Y[i]!=0){
            sub3=false;
        }

    }

    if(sub1){
        return subtask1(N, M, X, Y, W);
    }
    if(sub2){
        return subtask2(N, M, X, Y, W);
    }


    return subtask3(N, M, X, Y, W);
}

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:109:10: warning: variable 'sub3' set but not used [-Wunused-but-set-variable]
  109 |     bool sub3=true;
      |          ^~~~

• 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