제출 #1064595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064595		anango	휴가 (IOI14_holiday)	C++14	0 / 100	9 ms	604 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define int long long
//method:
//consider only going right, we'll try to compute the max obtainable with d days going to the right for each d
//now, let k be the number of cities we ever visit, and thus we get to actually see attractions of d-k cities
//we obviously visit the d-k cities with maximum attraction counts
//let visit(k,d) = max sum of visits for d with visiting the first k cities and actually opening d-k of them
//let opk[d] be the optimal number of cities to visit for d days
//note that opk[d+1]>=opk[d] (proved on paper)
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k,d)<=visit(k+1,d)
//to do this, we need a data structure that can insert values, also query the sum of the maximum t values for any t
//this can be done with a segment tree of suffix sums with lazy propagation with coordinate compression
//since we know all the attraction values in advance 
const int sz = 262144;
vector<int> revcoords;
class SegmentTree {
private:
    int tree[sz]; int lazy[sz];
};

vector<int> solve_for_all_d(int n, vector<int> weights) {
    //ignore the middle itself
    revcoords=vector<int>(n,-1);
    vector<pair<int,int>> coords;
    for (int i=0; i<n; i++) {
        coords.push_back({weights[i],i});
    }

    sort(coords.begin(), coords.end());
    for (int i=0; i<coords.size(); i++) {
        revcoords[coords[i].second] = i;
    }
}


long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
    if (d==0) {
        
    }
    return 0;
}

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

holiday.cpp: In function 'std::vector<long long int> solve_for_all_d(long long int, std::vector<long long int>)':
holiday.cpp:39:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0; i<coords.size(); i++) {
      |                   ~^~~~~~~~~~~~~~
holiday.cpp:42:1: warning: no return statement in function returning non-void [-Wreturn-type]
   42 | }
      | ^

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