제출 #396993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396993		leinad2	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	93 ms	8708 KiB

bridge

#include<bits/stdc++.h>
#define int long long
using namespace std;
char c, d;
int a, b, n, i, j, k;
long long ans, ans2=1e18, A[100010], B[100010], sum1, sum2;
struct st
{
    int a, b;
};
vector<st>v;vector<int>v1;
bool cmp(st a, st b)
{
    return a.a+a.b<b.a+b.b;
}
priority_queue<int>pq2;
priority_queue<int, vector<int>, greater<int> >pq1;
main()
{
    ios_base::sync_with_stdio(!cin.tie(NULL));
    for(cin>>k>>n;i++<n;)
    {
        cin>>c>>a>>d>>b;
        if(c==d)ans+=abs(b-a);
        else if(k==2)ans++,v.push_back({a, b});
        else ans++,v1.push_back(a),v1.push_back(b);
    }
    if(k==1)
    {
        sort(v1.begin(), v1.end());
        for(i=0;i<v1.size()/2;i++)ans-=v1[i];
        for(i=v1.size()/2;i<v1.size();i++)ans+=v1[i];
        cout<<ans;return 0;
    }
    sort(v.begin(), v.end(), cmp);
    for(i=0;i<v.size();i++)
    {
        if(v[i].a>v[i].b)swap(v[i].a, v[i].b);
        if(pq1.size()==0)
        {
            pq1.push(v[i].b);sum1+=v[i].b;
            pq2.push(v[i].a);sum2+=v[i].a;
        }
        else
        {
            if(v[i].b<=pq2.top())
            {
                a=pq2.top();
                pq1.push(a);sum1+=a;
                pq2.pop();sum2-=a;
                pq2.push(v[i].a);sum2+=v[i].a;
                pq2.push(v[i].b);sum2+=v[i].b;
            }
            else if(v[i].a<=pq1.top())
            {
                pq2.push(v[i].a);sum2+=v[i].a;
                pq1.push(v[i].b);sum1+=v[i].b;
            }
            else
            {
                a=pq1.top();
                pq2.push(a);sum2+=a;
                pq1.pop();sum1-=a;
                pq1.push(v[i].a);sum1+=v[i].a;
                pq1.push(v[i].b);sum1+=v[i].b;
            }
        }
        A[i+1]=sum1-sum2;
    }
    sum1=sum2=0;while(pq1.size())pq1.pop();while(pq2.size())pq2.pop();
    i=v.size();
    for(i--;i>=0;i--)
    {
        if(pq1.size()==0)
        {
            pq1.push(v[i].b);sum1+=v[i].b;
            pq2.push(v[i].a);sum2+=v[i].a;
        }
        else
        {
            if(v[i].b<=pq2.top())
            {
                a=pq2.top();
                pq1.push(a);sum1+=a;
                pq2.pop();sum2-=a;
                pq2.push(v[i].a);sum2+=v[i].a;
                pq2.push(v[i].b);sum2+=v[i].b;
            }
            else if(v[i].a<=pq1.top())
            {
                pq2.push(v[i].a);sum2+=v[i].a;
                pq1.push(v[i].b);sum1+=v[i].b;
            }
            else
            {
                a=pq1.top();
                pq2.push(a);sum2+=a;
                pq1.pop();sum1-=a;
                pq1.push(v[i].a);sum1+=v[i].a;
                pq1.push(v[i].b);sum1+=v[i].b;
            }
        }
        B[i]=sum1-sum2;
    }
    for(i=0;i<=v.size();i++)
    {
        ans2=min(ans2, A[i]+B[i]);
    }
    cout<<ans+ans2;
}

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

bridge.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main()
      |      ^
bridge.cpp: In function 'int main()':
bridge.cpp:31:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(i=0;i<v1.size()/2;i++)ans-=v1[i];
      |                 ~^~~~~~~~~~~~
bridge.cpp:32:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(i=v1.size()/2;i<v1.size();i++)ans+=v1[i];
      |                           ~^~~~~~~~~~
bridge.cpp:36:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(i=0;i<v.size();i++)
      |             ~^~~~~~~~~
bridge.cpp:105:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(i=0;i<=v.size();i++)
      |             ~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37