제출 #110849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110849		nvmdava	Salesman (IOI09_salesman)	C++17	27 / 100	1082 ms	64248 KiB

salesman

#include <bits/stdc++.h>
#define pb push_back
#define ss second
#define ff first
#define mp make_pair
using namespace std;

int u, d, s;

struct Container{
    set<pair<int, int> > hull;

    set<pair<int, int> > added;

    int get(int x){
        auto it = lower_bound(hull.begin(), hull.end(), mp(x, INT_MIN));
        if(it == hull.end()) return (--it) -> ss - d * (x - it -> ff);
        int res = it->ss - u * (it -> ff - x);
        if(it == hull.begin()) return res;
        res = max(res, (--it) -> ss - d * (x - it -> ff));
        return res;
    }

    void insert(int x, int val){
        added.insert({x, val});
        auto l = hull.insert({x, val}).ff;
        auto r = l;
        r++;
        while(r != hull.end() && r -> ss <= val - (r -> ff - x) * d)
            r = hull.erase(r);

        while(l != hull.begin() && (--l) -> ss <= val - (x - l -> ff) * u)
            l = hull.erase(l);
    }
    void clear(){
        added.clear();
    }
}  list1, list2;

map<int, vector<pair<int, int> > > day;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n>>u>>d>>s;

    for(int i = 1; i <= n; i++){
        int t, l, m;
        cin>>t>>l>>m;
        day[t].pb({l, m});
    }
    for(auto& x : day)
        sort(x.ss.begin(), x.ss.end());

    list1.insert(s, 0);
    list2.insert(s, 0);
    list1.clear();
    list2.clear();

    for(auto& x : day){
//        if(x.ff == 5) cout<<list1.get(110)<<' ';
        for(int i = 0; i < x.ss.size(); i++)
            list1.insert(x.ss[i].ff, x.ss[i].ss + list1.get(x.ss[i].ff));
        for(int i = x.ss.size() - 1; i >= 0; i--)
            list2.insert(x.ss[i].ff, x.ss[i].ss + list2.get(x.ss[i].ff));
        for(auto& add : list1.added)
            list2.insert(add.ff, add.ss);
        for(auto& add : list2.added)
            list1.insert(add.ff, add.ss);
        list1.clear();
        list2.clear();
//        if(x.ff == 5) cout<<list1.get(110)<<' ';
    }

    cout<<list1.get(s);
}

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

salesman.cpp: In function 'int main()':
salesman.cpp:65:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < x.ss.size(); i++)
                        ~~^~~~~~~~~~~~~

• Subtask 1: 27 / 100