Submission #888575

#	Time	Username	Problem	Language	Result	Execution time	Memory
888575		JakobZorz	Holiday (IOI14_holiday)	C++17	0 / 100	5060 ms	2392 KiB

holiday

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

// 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;
        for(int r=0;r<=d&&r<=(int)arr.size();r++){
            // c = how many cities you actually visit
            int c=d-r;
            vector<ll>vals;
            for(int i=0;i<r;i++){
                vals.push_back(arr[i]);
            }
            sort(vals.begin(),vals.end());
            reverse(vals.begin(),vals.end());
            ll res2=0;
            for(int i=0;i<c&&i<(int)vals.size();i++)
                res2+=vals[i];
            res1=max(res1,res2);
        }
        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;
        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);
            vector<ll>vals;
            for(int i=0;i<r;i++){
                vals.push_back(arr[i]);
            }
            sort(vals.begin(),vals.end());
            reverse(vals.begin(),vals.end());
            ll res2=0;
            for(int i=0;i<c&&i<(int)vals.size();i++)
                res2+=vals[i];
            res1=max(res1,res2);
        }
        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;
        if(d1<(int)val1.size()&&d2<(int)val2.size()){
            res=max(res,val1[d1]+val2[d2]);
        }
    }
    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));
}

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