제출 #1364043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364043		edga1	선물 (IOI25_souvenirs)	C++20	21 / 100	1080 ms	772 KiB

souvenirs

#include <bits/stdc++.h>
#include "souvenirs.h"
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;

void buy_souvenirs(int n, long long P0) {
    vector<ll> b(n,0), mi(n), ma(n);
    ma[0]=mi[0]=P0;
    for(int i=n-1; i>0; i--){
        mi[i]=n-i;
        ma[i]=P0-i;
    }
    int pos=n-1;
    vector<pair<ll,pair<vector<int>,ll>>> pt;
    while(pos!=0){
        if(ma[pos]==mi[pos]){
            pos--;
            continue;
        }
        pair<vector<int>,ll> res=transaction(ma[pos]);
        pt.pb({ma[pos],res});
        for(auto au : res.fi) b[au]++;
        int e=1;
        while(e){
            e=0;
            for(auto au : pt){
                ll c=au.fi, r=au.se.se;
                vector<int> s=au.se.fi;
                for(int i=0; i<s.size(); i++){
                    if(ma[s[i]]==mi[s[i]]) continue;
                    ll cma=r, cmi=r;
                    for(int j=0; j<s.size(); j++){
                        if(i==j) continue;
                        cmi+=mi[s[j]];
                        cma+=ma[s[j]];
                    }
                    if(ma[s[i]]>c-cmi){
                        ma[s[i]]=c-cmi;
                        e=1;
                        for(int j=s[i]+1; j<n; j++){
                            ma[j]=min(ma[j],ma[j-1]-1);
                        }
                    }
                    if(mi[s[i]]<c-cma){
                        mi[s[i]]=c-cma;
                        e=1;
                        for(int j=s[i]-1; j>0; j--){
                            mi[j]=max(mi[j],mi[j+1]+1);
                        }
                    }
                }
            }
        }
    }
    for(int i=1; i<n; i++){
        for(int j=0; j<i-b[i]; j++){
            pair<vector<int>,ll> res=transaction(ma[i]);
        }
    }
    return;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 4 / 4
• 서브태스크 2: 3 / 3
• 서브태스크 3: 14 / 14
• 서브태스크 4: 0 / 18
• 서브태스크 5: 0 / 28
• 서브태스크 6: 0 / 33