제출 #86764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86764		Mercenary	금 캐기 (IZhO14_divide)	C++11	0 / 100	70 ms	10584 KiB

divide

#include<bits/stdc++.h>
#define pb push_back
#define brokenheart "TEST"
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 5;
#define int ll

int n;
int x[maxn] , r[maxn] , g[maxn] , dis[maxn];
int bit[maxn] , cost[maxn] , c[maxn] , sum[maxn];
vector<pair<int,int>> v;
void enter()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> x[i] >> g[i] >> r[i];
    for(int i = 1 ; i < n ; ++i)
        dis[i] = x[i + 1] - x[i];
    for(int i = 1 ; i < n ; ++i){
        cost[i] = cost[i - 1] + dis[i] - r[i];
        v.pb({cost[i],i});
    }
    v.pb({0,0});
    sort(v.begin(),v.end());
    for(int i = 1 ; i <= n ; ++i)
        sum[i] = sum[i - 1] + g[i];
    int cnt = 1;
    c[v[0].second] = 1;
    vector<pair<int,int>> v1;
    v1.push_back(v[0]);
    for(int i = 1 ; i < v.size() ; ++i)
    {
        if(v[i].first == v[i - 1].first)c[v[i].second] = cnt;
        else c[v[i].second] = ++cnt ,v1.push_back(v[i]);
    }
    v = v1;
}

void update(int pos , int x)
{
    for( ; pos < maxn ; pos += pos & -pos)
        bit[pos] = min(bit[pos],x);
}

int query(int pos)
{
    int res = maxn;
    for( ; pos > 0 ; pos &= pos - 1)
        res = min(res , bit[pos]);
    return res;
}

void solve()
{
    fill_n(bit , maxn , maxn);
    ll res = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        int pos = upper_bound(v.begin(),v.end(),make_pair(r[i] - cost[i - 1] , 0ll)) - v.begin();
        int ans = query(pos);
        if(ans != maxn)res = max(res , sum[i] - sum[ans]);
        if(i != n)update(c[i] , i - 1);
        res = max(res , g[i]);
    }
    cout << res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    if(fopen(brokenheart".INP","r"))
        freopen(brokenheart".INP","r",stdin) ,
        freopen(brokenheart".OUT","w",stdout);
    enter();
    solve();
}

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

divide.cpp: In function 'void enter()':
divide.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1 ; i < v.size() ; ++i)
                     ~~^~~~~~~~~~
divide.cpp: In function 'int32_t main()':
divide.cpp:75:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(brokenheart".INP","r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(brokenheart".OUT","w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
divide.cpp:75:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 0 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52