Submission #1007413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007413		Ahmed57	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	348 KiB

tickets

#include "bits/stdc++.h"
#include "tickets.h"

using namespace std;
long long find_maximum(int k,vector<vector<int>> x){
    int n = x.size();
    int m = x[0].size();
    vector<vector<int>> vis(n,vector<int>(m,-1));
    long long fin = 0;
    for(int i = 0;i<k;i++){
        int mi[n],ma[n];
        vector<array<int,5>> v;
        long long overall = -1e9;
        for(int j = 0;j<n;j++){
            mi[j] = 1e9;
            ma[j] = -1e9;
            int MI = 0;
            int MA = 0;
            for(int w = 0;w<m;w++){
                if(vis[j][w]!=-1)continue;
                if(mi[j]>x[j][w]){
                    mi[j] = x[j][w];
                    MI = w;
                }if(ma[j]<x[j][w]){
                    ma[j] = x[j][w];
                    MA = w;
                }
            }
            v.push_back({mi[j],ma[j],MI,MA,j});
        }
        sort(v.begin(),v.end());
        for(int j = n/2-1;j<n;j++){
            int lrg = 0 , sml = 0;
            for(int w = j+1;w<n;w++){
                lrg+=v[w][1];
            }   
            vector<array<int,5>> na;
            for(int w = j;w>=0;w--){
                sml+=v[w][0];
                na.push_back({v[w][1],v[w][0],v[w][3],v[w][2],v[w][4]});
            }
            sort(na.begin(),na.end());
            reverse(na.begin(),na.end());
            int rem = n-j-1;
            rem = n/2 -rem;
            int la = 1e9;
            for(int w = 0;w<rem;w++){
                sml-=na[w][1];
                lrg+=na[w][0];
                la = na[w][0];
            }
            if(la>=v[j][0]){
                if(overall>lrg-sml){
                    for(int w = 0;w<n;w++){
                        for(int s = 0;s<m;s++){
                            if(vis[w][s]==i)vis[w][s] = -1;
                        }
                    }
                    overall = lrg-sml;
                    for(int w = j+1;w<n;w++){
                        vis[v[w][4]][v[w][3]] = i;
                    }
                    for(int w = 0;w<na.size();w++){
                        if(w<rem){
                            vis[v[w][4]][v[w][2]] = i;
                        }else{
                            vis[v[w][4]][v[w][3]] = i;
                        }
                    }
                }
            }
        }
        fin+=overall;
    }
    allocate_tickets(vis);
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:63:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                     for(int w = 0;w<na.size();w++){
      |                                   ~^~~~~~~~~~
tickets.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
   76 | }
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10