Submission #1054212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054212		FaustasK	Palembang Bridges (APIO15_bridge)	C++14	31 / 100	2092 ms	4804 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

struct gyventojas
{
    char p;
    int s;
    char q;
    int t;
};

const int maxn = 100000;

int k, n;
gyventojas M[maxn];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> k >> n;
    long long A_puse = 0;
    long long B_puse = 0;
    vector <int> reikalingi;
    vector <int> nereikalingi;
    vector <int> medianai;
    for(int i = 0; i<n; i++)
    {
        cin >> M[i].p >> M[i].s >> M[i].q >> M[i].t;
        if(M[i].p != M[i].q)
        {
            reikalingi.push_back(i);
            medianai.push_back(M[i].s);
            medianai.push_back(M[i].t);
            if(M[i].p == 'A' && M[i].q == 'B')
            {
                A_puse += M[i].s;
                B_puse += M[i].t;
            }
            else
            {
                A_puse += M[i].t;
                B_puse += M[i].s;
            }
        }
        else nereikalingi.push_back(i);
    }
    int kiek = reikalingi.size();
    long long ats = 0;
    if(kiek>0)
    {
        /*long long suma = A_puse + B_puse;
        double liekana1 = suma%2;
        //cout << liekana1 << endl;
        liekana1/=2;
        suma/=2;
        //cout << suma << endl;
        //cout << liekana1 << endl;
        double liekana2 = suma%kiek;
        //cout << liekana2 << endl;
        liekana2 += liekana1;
        //cout << liekana2 << endl;
        liekana2/=kiek;
        //cout << liekana2 << endl;
        suma/=kiek;
        //cout << suma << endl;
        double dsuma = suma + liekana2;
        //cout << dsuma << endl;
        int tiltas = round(dsuma);
        //cout << ats;*/
        if(k == 1)
        {
            sort(medianai.begin(), medianai.end());
            int tiltas = medianai[medianai.size()/2];
            for(int i = 0; i<reikalingi.size(); i++)
            {
                int j = reikalingi[i];
                ats += abs(M[j].s - tiltas) + abs(M[j].t - tiltas);
            }
        }
        else
        {
            ats = 1000000000000000;
            for(int i = 0; i<medianai.size(); i++)
            {
                for(int j = 0; j<medianai.size(); j++)
                {
                    if(i == j) continue;
                    int tiltas1 = medianai[i];
                    int tiltas2 = medianai[j];
                    long long maz_ats = 0;
                    for(int f = 0; f<reikalingi.size(); f++)
                    {
                        int x = reikalingi[f];
                        int a1 = abs(M[x].s - tiltas1) + abs(M[x].t - tiltas1);
                        int a2 = abs(M[x].s - tiltas2) + abs(M[x].t - tiltas2);
                        maz_ats += min(a1, a2);
                    }
                    ats = min(ats, maz_ats);
                }
            }
        }
    }
    for(int i = 0; i<nereikalingi.size(); i++)
    {
        int j = nereikalingi[i];
        ats += abs(M[j].s - M[j].t);
    }
    cout << ats + reikalingi.size();
    return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:75:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int i = 0; i<reikalingi.size(); i++)
      |                            ~^~~~~~~~~~~~~~~~~~
bridge.cpp:84:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int i = 0; i<medianai.size(); i++)
      |                            ~^~~~~~~~~~~~~~~~
bridge.cpp:86:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 for(int j = 0; j<medianai.size(); j++)
      |                                ~^~~~~~~~~~~~~~~~
bridge.cpp:92:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     for(int f = 0; f<reikalingi.size(); f++)
      |                                    ~^~~~~~~~~~~~~~~~~~
bridge.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i = 0; i<nereikalingi.size(); i++)
      |                    ~^~~~~~~~~~~~~~~~~~~~

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