제출 #1028144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028144		dozer	Holiday (IOI14_holiday)	C++14	100 / 100	1585 ms	20316 KiB

holiday

#include"holiday.h"
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define ll long long
#define MAXN 200005
#define LOGN 20

const int modulo = 1e9+7;
const ll INF = 2e18 + 7;


void compute_dc_dp2(int l, int r, int L, int R, ll curr_sum, int flag, vector<int> &arr, vector<ll> &dp){
    vector<array<int, 4>> ranges, tmp;
    ranges.pb({l, r, L, R});
    for (int i = 0; i < LOGN; i++){
        auto it = 0;
        multiset<int> curr[2];
        curr[1].insert(arr[it]);
        ll curr_sum = 0;
        tmp.clear();
        for (auto j : ranges){
            int l = j[0], r = j[1], sl = j[2], sr = j[3];
            int mid = (l + r) / 2;
            pair<ll, ll> opt = {0, sl};
            int start = it;
            while(it <= sr){
                if (it * flag > mid) break;
                if (it != start) { //umm, not fully sure of this but whatever
                    curr[1].insert(arr[it]); 
                }
                while(curr[0].size() < mid - flag * it && !curr[1].empty()){
                    int top = *curr[1].rbegin();
                    curr[1].erase(curr[1].find(top));
                    curr_sum += top;
                    curr[0].insert(top);
                }

                while(curr[0].size() > mid - flag * it){
                    int top = *curr[0].begin();
                    curr[0].erase(curr[0].begin());
                    curr_sum -= top;
                    curr[1].insert(top);
                }

                while(!curr[0].empty() && !curr[1].empty() && *curr[0].begin() < *curr[1].rbegin()){
                    int top = *curr[1].rbegin();
                    curr[1].erase(curr[1].find(top));
                    curr_sum += top;
                    curr[0].insert(top);

                    top = *curr[0].begin();
                    curr[0].erase(curr[0].begin());
                    curr_sum -= top;
                    curr[1].insert(top);
                }
                if (it >= sl) opt = max(opt, {curr_sum, it});
                it++;
            }
            int pos = opt.nd;
            dp[mid] = opt.st;
            //cout<<mid<<" : "<<sp<<sl<<sp<<sr<<sp<<sp<<curr_sum<<sp<<curr[0].size()<<sp<<curr[1].size()<<sp<<opt.st<<sp<<opt.nd<<endl;
            if (l < mid) tmp.pb({l, mid - 1, sl, pos});
            if (r > mid) tmp.pb({mid + 1, r, pos, sr});
            it--;
        }
        swap(tmp, ranges);
    }
}


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<ll> lft[2], rgt[2];
    for (int i = 0; i < 2; i++){
        lft[i].resize(d + 1, 0);
        rgt[i].resize(d + 1, 0);
    }
 
    vector<int> L, R;
    L.pb(0), R.pb(0);
 
    for (int i = start - 1; i >= 0; i--){
        L.pb(attraction[i]);
    }
 
 
    compute_dc_dp2(0, d, 0, L.size() - 1, 0, 1, L, lft[0]);
    compute_dc_dp2(0, d, 0, L.size() - 1, 0, 2, L, lft[1]);
 
 
    for (int i = start + 1; i < n; i++)
        R.pb(attraction[i]);
 
    compute_dc_dp2(0, d, 0, R.size() - 1, 0, 1, R, rgt[0]);
    compute_dc_dp2(0, d, 0, R.size() - 1, 0, 2, R, rgt[1]);
 /*
    for (int i = 0; i < d; i++)
        cout<<i<<sp<<1<<" : "<<lft[0][i]<<endl;*/
    ll ans = 0;
    for (int i = 0; i <= d; i++){
        ll t1 = lft[0][i] + rgt[1][d - i];
        ll t2 = lft[1][i] + rgt[0][d - i];
        ll t3 = 0, t4 = 0;
        if (i < d) t3 = lft[0][i] + rgt[1][d - i - 1] + attraction[start];
        if (i < d) t4 = lft[1][i] + rgt[0][d - i - 1] + attraction[start];
        ans = max(ans, max(t1, t2));
        ans = max(ans, max(t3, t4));
    }
    return ans;
}

/*
int main() {
    fileio();
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
	n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
    return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'void compute_dc_dp2(int, int, int, int, long long int, int, std::vector<int>&, std::vector<long long int>&)':
holiday.cpp:43:38: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |                 while(curr[0].size() < mid - flag * it && !curr[1].empty()){
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
holiday.cpp:50:38: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |                 while(curr[0].size() > mid - flag * it){
      |                       ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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