Submission #888577

#	Time	Username	Problem	Language	Result	Execution time	Memory
888577		JakobZorz	Holiday (IOI14_holiday)	C++17	24 / 100	5066 ms	2888 KiB

holiday

#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;

struct DS{
    multiset<ll>vals;
    ll sum=0;
    
    void add(int val){
        vals.insert(val);
        sum+=val;
    }
    
    ll get(int k){
        while(vals.size()>k){
            sum-=*vals.begin();
            vals.erase(vals.begin());
        }
        return sum;
    }
};

// if you can only walk in one direction
// return a[d] = most score if you have d days
vector<ll>get3(vector<int>arr){
    vector<ll>res;
    for(int d=0;d<=2*(int)arr.size();d++){
        // r = how far you go
        ll res1=0;
        DS ds;
        for(int r=0;r<=d&&r<=(int)arr.size();r++){
            // c = how many cities you actually visit
            int c=d-r;
            if(r)
                ds.add(arr[r-1]);
            res1=max(res1,ds.get(c));
        }
        res.push_back(res1);
    }
    return res;
}

// if you can only walk in one direction and have to go back
// return a[d] = most score if you have d days
vector<ll>get2(vector<int>arr){
    vector<ll>res;
    for(int d=0;d<=3*(int)arr.size();d++){
        // r = how far you go
        ll res1=0;
        DS ds;
        for(int r=0;2*(r-1)<=d&&r<=(int)arr.size();r++){
            // c = how many cities you actually visit
            int c=d-2*(r-1);
            if(r)
                ds.add(arr[r-1]);
            res1=max(res1,ds.get(c));
        }
        res.push_back(res1);
    }
    return res;
}

// if you first start walking to the left and then right
ll get1(vector<int>arr,int d,int s){
    int n=(int)arr.size();
    vector<int>arr1,arr2;
    for(int i=s;i>=0;i--)
        arr1.push_back(arr[i]);
    for(int i=s+1;i<n;i++)
        arr2.push_back(arr[i]);
    
    vector<ll>val1=get2(arr1),val2=get3(arr2);
    /*cout<<"val1 ";
    for(ll i:val1)
        cout<<i<<" ";
    cout<<"\n";
    
    cout<<"val2 ";
    for(ll i:val2)
        cout<<i<<" ";
    cout<<"\n";*/
    
    ll res=0;
    for(int d1=0;d1<=d;d1++){
        int d2=d-d1;
        res=max(res,val1[min(d1,(int)val1.size()-1)]+val2[min(d2,(int)val2.size()-1)]);
    }
    return res;
}

ll findMaxAttraction(int n,int start,int d,int attraction[]){
    vector<int>arr;
    for(int i=0;i<n;i++)
        arr.push_back(attraction[i]);
    
    ll res=get1(arr,d,start);
    reverse(arr.begin(),arr.end());
    
    return max(res,get1(arr,d,n-start-1));
}

Compilation message (stderr)

holiday.cpp: In member function 'll DS::get(int)':
holiday.cpp:19:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         while(vals.size()>k){
      |               ~~~~~~~~~~~^~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53