제출 #763679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763679		Ahmed57	휴가 (IOI14_holiday)	C++17	47 / 100	705 ms	1836 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>

using namespace std;
long long seg[9001] , cnt[9001];
void update(int p,int l,int r,int idx,long long val){
    if(l==r){
        seg[p]+=val;
        cnt[p]++;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    cnt[p] = cnt[p*2]+cnt[p*2+1];
    seg[p] = seg[p*2]+seg[p*2+1];
}
long long query(int p,int l,int r,long long num){
    if(l==r){
        if(cnt[p]==0){
            return 0;
        }
        return (seg[p]/cnt[p])*min(num,cnt[p]);
    }
    int md = (l+r)/2;
    if(num>=cnt[p*2+1]){
        return seg[p*2+1]+query(p*2,l,md,num-cnt[p*2+1]);
    }else{
        return query(p*2+1,md+1,r,num);
    }
}
long long int findMaxAttraction(int n, int start, int d,
int attraction[]){
    if(start==0){
        priority_queue<long long> q;
        long long sum = 0 , ma = 0;
        for(int i = 0;i<n;i++){
            q.push(-attraction[i]);
            sum+=attraction[i];
            while(!q.empty()&&q.size()>(d-i)){
                sum+=q.top();
                q.pop();
            }
            ma = max(ma,sum);
        }
        return ma;
    }
    map<int,int> comp,sav;
    for(int i = 0;i<n;i++){
        comp[attraction[i]]++;
    }
    int z = 0;
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    long long ma = 0;
    for(int i = 0;i<=start;i++){
        memset(seg,0,sizeof seg);
        memset(cnt,0,sizeof cnt);
        for(int j = i;j<start;j++){
            update(1,1,n,sav[attraction[j]],attraction[j]);
        }
        for(int j = start;j<n;j++){
            update(1,1,n,sav[attraction[j]],attraction[j]);
            long long rem = d-(min(abs(start-i),abs(start-j))*2)-max(abs(start-i),abs(start-j));
            if(rem<=0)continue;
            ma = max(ma,query(1,1,n,rem));
        }
    }
    return ma;
}
/*
int main(){
    int S[] = {10,2,20,30,1};

    cout<<findMaxAttraction(5,2,7,S);
}*/

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

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:41:39: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             while(!q.empty()&&q.size()>(d-i)){
      |                               ~~~~~~~~^~~~~~

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