Submission #1119353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119353		GoodkNight	Catfish Farm (IOI22_fish)	C++17	0 / 100	43 ms	14516 KiB

fish

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+8;
struct f{
    int y;
    int w;
    long long pod;
    long long lewo;
    long long prawo;
};
bool operator< (f a, f b){
    if(a.y < b.y) return 1;
    return 0;
}
vector<f> fish[N];

long long arzad[N];
long long brzad[N];
long long crzad[N];

f pusta;

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> z){
    f nowy;
    for(int i=0; i<m; i++){
        nowy.y = y[i];
        nowy.w = z[i];
        nowy.lewo = 0;
        nowy.pod = 0;
        nowy.prawo=0;
        fish[x[i]].push_back(nowy); 
    }
    pusta.w = 0;
    pusta.y = N+2;
    pusta.lewo=0;
    pusta.prawo=0;
    pusta.pod=0;
    for(int i=0; i<n; i++) fish[i].push_back(pusta);
    for(int i=0; i<n; i++){
        sort(fish[i].begin(), fish[i].end());
        arzad[i]=0;
        brzad[i]=0;
        crzad[i]=0;
        long long suma=0;
        for(int j=0; j<fish[i].size(); j++){
            fish[i][j].pod = suma;
            suma+= fish[i][j].w;
        }
    }
    for(int i=0; i<n-1; i++){
        long long lesum=0, prsum=0;
        for(int le=0, pr=0; le<fish[i].size()||pr<fish[i+1].size(); ){
            if(fish[i][le].y < fish[i+1][pr].y){
                fish[i][le].prawo = prsum;
                lesum = fish[i][le].pod;
                le++;
                continue;
            }
            if(fish[i][le].y > fish[i+1][pr].y){
                fish[i+1][pr].lewo = lesum;
                prsum = fish[i+1][pr].pod;
                pr++;
                continue;
            }
            lesum = fish[i][le].pod;
            prsum = fish[i+1][pr].pod;
            fish[i][le].prawo = prsum;
            fish[i+1][pr].lewo = lesum;
            le++;
            pr++;
        }
    }
    arzad[0] = fish[0][fish[0].size()-1].prawo;
    brzad[0] = 0;
    crzad[0]=0;
    for(int i=0; i<fish[1].size(); i++){
        long long bi = fish[1][i].lewo - fish[1][i].pod;
        long long ci = max(arzad[0] - fish[1][i].pod, bi + fish[1][i].pod);
        long long ai = ci + fish[1][i].prawo;
        arzad[1] = max(arzad[1], ai);
        brzad[1] = max(brzad[1], bi);
        crzad[1] = max(crzad[1], ci);
    }
    //cout << arzad[0]<<" "<<brzad[0]<<" "<<crzad[0]<<"\n";
    //cout << arzad[1]<<" "<<brzad[1]<<" "<<crzad[1]<<"\n";
    for(int j=2; j<n; j++){
        for(int i=0; i<fish[j].size(); i++){
            long long bi = fish[j][i].lewo + brzad[j-1];
            bi = max(bi, arzad[j-2]);
            bi = max(bi, crzad[j-2] + fish[j][i].lewo);
            bi -= fish[i][j].pod;
            long long ci = max(arzad[0] - fish[j][i].pod, bi + fish[j][i].pod);
            long long ai = ci + fish[j][i].prawo;
            arzad[j] = max(arzad[j], ai);
            brzad[j] = max(brzad[j], bi);
            crzad[j] = max(crzad[j], ci);
        }
            //cout << arzad[j]<<" "<<brzad[j]<<" "<<crzad[j]<<"\n";
    }
    long long wynik = 0;
    wynik = max(wynik, arzad[n-1]);
    wynik = max(wynik, brzad[n-1]);
    wynik = max(wynik, crzad[n-1]);
    return wynik;
}

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:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<f>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0; j<fish[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~
fish.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<f>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int le=0, pr=0; le<fish[i].size()||pr<fish[i+1].size(); ){
      |                             ~~^~~~~~~~~~~~~~~
fish.cpp:52:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<f>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int le=0, pr=0; le<fish[i].size()||pr<fish[i+1].size(); ){
      |                                                ~~^~~~~~~~~~~~~~~~~
fish.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<f>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0; i<fish[1].size(); i++){
      |                  ~^~~~~~~~~~~~~~~
fish.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<f>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i=0; i<fish[j].size(); i++){
      |                      ~^~~~~~~~~~~~~~~

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