제출 #695091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695091		yogesh_sane	휴가 (IOI14_holiday)	C++17	7 / 100	359 ms	65536 KiB

holiday

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <unordered_map>
using namespace std;
int const MAXN = 1e5;

long long subtask1(int n, int start, int d, int attraction[]){
    long long ans = 0;
    for(int mask = 1; mask < (1<<n); mask++){
        vector<int> cities;
        for(int bit = 0; bit < n; bit++){
            if(mask&(1<<bit)){
                cities.push_back(bit);
            }
        }
        int curr_city = start;
        int tour_days = 0;
        long long ans_curr = 0;
        for(auto city : cities){
            tour_days += abs(curr_city-city)+1;
            ans_curr += attraction[city];
            curr_city = city;
        }
        if(tour_days <= d)
            ans = max(ans, ans_curr);
        reverse(cities.begin(), cities.end());
        curr_city = start;
        tour_days = 0;
        ans_curr = 0;
        for(auto city : cities){
            tour_days += abs(curr_city-city)+1;
            ans_curr += attraction[city];
            curr_city = city;
        }
        if(tour_days <= d)
            ans = max(ans, ans_curr);
    }
    return ans;
}
int max_city, max_day;
unordered_map<int,unordered_map<int, long long>> dp[2];
long long solve(int city, int day, bool visited, int attraction[]){
    if(city == max_city)
        return 0;
    if(day > max_day)
        return 0;
    if(max_day-day >= (max_city-city)*2-1)
        return accumulate(attraction+city, attraction+max_city,0);
    auto it_city = dp[visited].find(city);
    if(it_city != dp[visited].end()){
        auto it_day = dp[visited][city].find(day);
        if(it_day != dp[visited][city].end())
            return dp[visited][city][day];
    }
    long long ans = 0;
    if(visited){
        ans += solve(city+1,day+1,false,attraction);
    }else{
        long long visit = attraction[city] + solve(city,day+1,true,attraction);
        long long travel = solve(city+1,day+1,false,attraction);
        ans += max(visit,travel);
    }
    dp[visited][city][day] = ans;
    return ans;
}
long long subtask2(int n, int start, int d, int attraction[]){
    max_city = n;
    max_day = d;
    return solve(0,0,false,attraction);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(n <= 20){
        return subtask1(n,start,d,attraction);
    }else if(start == 0){
        return subtask2(n,start,d,attraction);
    }
    return 0;
}

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