Submission #363358

#	Time	Username	Problem	Language	Result	Execution time	Memory
363358		denkendoemeer	Arranging Tickets (JOI17_arranging_tickets)	C++14	100 / 100	1313 ms	16740 KiB

arranging_tickets

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<int,int>>g[200005];
ll sum[200005],maxi[200005],h[200005],t[200005];
int nr,n,m;
priority_queue<pair<int,int>>pq;
bool calc(ll k)
{
    int i;
    ll s=0;
    for(i=0;i<n;i++){
        h[i]=min(h[i],k);
        t[i]=0;
    }
    h[nr]=0;
    while(!pq.empty())
        pq.pop();
    for(i=1;i<=nr;i++){
        for(auto it:g[i])
            if (it.first>nr)
                pq.push(it);
        s=s+h[i-1]-h[i];
        while(s){
            if (pq.empty())
                return 0;
            pair<int,int>nod=pq.top();
            pq.pop();
            if (nod.second>=s){
                nod.second-=s;
                t[nod.first]-=s;
                pq.push(nod);
                s=0;
            }
            else{
                t[nod.first]-=nod.second;
                s-=nod.second;
            }
        }
    }
    for(i=1;i<n;i++){
        t[i]=t[i]+t[i-1];
        if (t[i]+h[i]<0)
            return 0;
    }
    return 1;
}
bool verif(ll k)
{
    ll i,j,val=maxi[nr]-k,num=k/2;
    for(i=val;i<=val+1;i++){
        for(j=0;j<n;j++)
            h[j]=(i+k-maxi[j])/2;
        if (h[0]<i)
            continue;
        if (calc(i))
            return 1;
    }
    return 0;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i,a,b,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        if (a>b)
            swap(a,b);
        g[a].push_back({b,c});
        sum[a]+=c;
        sum[b]-=c;
    }
    ll ma=-1;
    nr=-1;
    for(i=1;i<n;i++){
        sum[i]+=sum[i-1];
        if (ma<sum[i]){
            ma=sum[i];
            nr=i;
        }
    }
    for(i=1;i<=nr;i++)
        maxi[i]=max(maxi[i-1],sum[i]);
    for(i=n-1;i>=nr;i--)
        maxi[i]=max(maxi[i+1],sum[i]);
    ll st=0,dr=ma-1,mij,ans=ma;
    while(st<=dr){
        mij=(st+dr)/2;
        if (verif(mij)){
            ans=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
arranging_tickets.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15