Submission #693289

#	Time	Username	Problem	Language	Result	Execution time	Memory
693289		NemanjaSo2005	Carnival Tickets (IOI20_tickets)	C++14	41 / 100	550 ms	71048 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#define ll long long
using namespace std;
ll N,M,K,koliko[1505][1505],p1[1505],p2[1505],suma[1505];
struct sslog{
   int vred,i,j;
}sniz[1505];
bool spov(sslog a,sslog b){
   return a.vred<b.vred;
}
struct slog{
   ll v2,v1,suma;
   int i,j1,j2;
} niz[1505];
bool cmp(slog a,slog b){
   if(a.v1+a.v2<b.v1+b.v2)
      return true;
   if(a.v1+a.v2>b.v1+b.v2)
      return false;
   if(a.suma<b.suma)
      return true;
   if(a.suma>b.suma)
      return false;
   return (a.v1-a.v2)>(b.v1-b.v2);
}
vector<vector<int>> kako;
ll find_maximum(int k,vector<vector<int>> d){
   kako=d;
   for(int i=0;i<kako.size();i++)
      for(int j=0;j<kako[i].size();j++)
         kako[i][j]=-1;
   K=k;
   N=d.size();
   M=d[0].size();
   for(int i=1;i<=N;i++)
      for(int j=1;j<=M;j++){
         koliko[i][j]=d[i-1][j-1];
         suma[i]+=koliko[i][j];
      }
   for(int i=1;i<=N;i++){
      p1[i]=1;
      p2[i]=M;
   }
   ll res=0;
   for(int dan=0;dan<K;dan++){/*
      for(int i=1;i<=N;i++)
         cout<<p1[i]<<" pok "<<p2[i]<<endl;*/
      for(int i=1;i<=N;i++){
         niz[i].v1=koliko[i][p1[i]];
         niz[i].v2=koliko[i][p2[i]];
         niz[i].j1=p1[i]-1;
         niz[i].j2=p2[i]-1;
         niz[i].suma=suma[i];
         niz[i].i=i-1;
      }
      sort(niz+1,niz+1+N,cmp);
      //for(int i=1;i<=N;i++)
       //  cout<<niz[i].v1<<" "<<niz[i].v2<<endl;
      for(int i=1;i<=N/2;i++){
         res-=niz[i].v1;
         suma[niz[i].i+1]-=niz[i].v1;
         p1[niz[i].i+1]++;
         kako[niz[i].i][niz[i].j1]=dan;
      }
      for(int i=N/2+1;i<=N;i++){
         res+=niz[i].v2;
         suma[niz[i].i+1]-=niz[i].v2;
         p2[niz[i].i+1]--;
         //cout<<niz[i].i<<endl;
         kako[niz[i].i][niz[i].j2]=dan;
      }
   }
   allocate_tickets(kako);
   return res;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int i=0;i<kako.size();i++)
      |                ~^~~~~~~~~~~~
tickets.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       for(int j=0;j<kako[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

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