oj.uz

Submission #1109940

# Submission time Handle Problem Language Result Execution time Memory
1109940 2024-11-08T07:30:53 Z simona1230 Palembang Bridges (APIO15_bridge) C++17
63 / 100
 2000 ms 7356 KB 
#include <bits/stdc++.h>
using namespace std;

long long k,n,num,other;
pair<long long,long long> p[100001];

bool cmp(pair<long long,long long> p1,pair<long long,long long> p2)
{
    return p1.first+p1.second<p2.first+p2.second;
}

void read()
{
    cin>>k>>n;
    for(long long i=1;i<=n;i++)
    {
        char c1,c2;
        long long x,y;
        cin>>c1>>x>>c2>>y;

        if(c1==c2)other+=abs(x-y);
        else
        {
            num++;
            p[num]={min(x,y),max(x,y)};
        }
    }

    sort(p+1,p+num+1,cmp);

    if(num==0)
    {
        cout<<other<<endl;
        exit(0);
    }
}

void solve1()
{
    vector<long long> v;

    for(long long i=1;i<=num;i++)
    {
        v.push_back(p[i].first);
        v.push_back(p[i].second);
    }

    sort(v.begin(),v.end());

    long long x=v[v.size()/2];

    long long ans=other+num;
    for(long long i=0;i<v.size();i++)
    {
        ans+=abs(v[i]-x);
    }

    cout<<ans<<endl;
}

void solve2()
{
    long long ans=1e18;
    if(num==1)
    {
        cout<<other+1+p[1].second-p[1].first<<endl;
        exit(0);
    }

    for(long long i=1;i<num;i++)
    {
        vector<long long> v1,v2;
        for(long long j=1;j<=num;j++)
        {
            if(j<=i)
            {
                v1.push_back(p[j].first);
                v1.push_back(p[j].second);
            }
            else
            {
                v2.push_back(p[j].first);
                v2.push_back(p[j].second);
            }
        }

        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());

        long long x1=v1[v1.size()/2];
        long long x2=v2[v2.size()/2];

        long long curr=0;
        for(long long j=0;j<v1.size();j++)
            curr+=abs(v1[j]-x1);
        for(long long j=0;j<v2.size();j++)
            curr+=abs(v2[j]-x2);

        ans=min(ans,curr+other+num);
    }
    cout<<ans<<endl;
}

int main()
{
    read();
    if(k==1)solve1();
    else solve2();
    return 0;
}

/*
 2 5
 B 0 A 4
 B 1 B 3
 A 5 B 7
 B 2 A 6
 B 1 A 7

1 3
A 1 B 1
A 5 B 5
A 6 B 6
*/

Compilation message

bridge.cpp: In function 'void solve1()':
bridge.cpp:53:24: 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]
   53 |     for(long long i=0;i<v.size();i++)
      |                       ~^~~~~~~~~
bridge.cpp: In function 'void solve2()':
bridge.cpp:94: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]
   94 |         for(long long j=0;j<v1.size();j++)
      |                           ~^~~~~~~~~~
bridge.cpp:96: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]
   96 |         for(long long j=0;j<v2.size();j++)
      |                           ~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 464 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 35 ms 5820 KB Output is correct
13 Correct 84 ms 7356 KB Output is correct
14 Correct 57 ms 6108 KB Output is correct
15 Correct 51 ms 3852 KB Output is correct
16 Correct 60 ms 6852 KB Output is correct
17 Correct 84 ms 7356 KB Output is correct
18 Correct 71 ms 7100 KB Output is correct
19 Correct 77 ms 7356 KB Output is correct
20 Correct 60 ms 6848 KB Output is correct
21 Correct 68 ms 7100 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 21 ms 448 KB Output is correct
14 Correct 62 ms 336 KB Output is correct
15 Correct 73 ms 336 KB Output is correct
16 Correct 3 ms 336 KB Output is correct
17 Correct 18 ms 336 KB Output is correct
18 Correct 12 ms 336 KB Output is correct
19 Correct 32 ms 336 KB Output is correct
20 Correct 31 ms 336 KB Output is correct
21 Correct 57 ms 336 KB Output is correct
22 Correct 22 ms 336 KB Output is correct
23 Correct 20 ms 336 KB Output is correct
24 Correct 21 ms 504 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 26 ms 336 KB Output is correct
14 Correct 63 ms 524 KB Output is correct
15 Correct 78 ms 336 KB Output is correct
16 Correct 3 ms 336 KB Output is correct
17 Correct 18 ms 496 KB Output is correct
18 Correct 11 ms 504 KB Output is correct
19 Correct 21 ms 528 KB Output is correct
20 Correct 21 ms 336 KB Output is correct
21 Correct 56 ms 336 KB Output is correct
22 Correct 30 ms 336 KB Output is correct
23 Correct 23 ms 512 KB Output is correct
24 Correct 23 ms 508 KB Output is correct
25 Execution timed out 2071 ms 6460 KB Time limit exceeded
26 Halted 0 ms 0 KB -