oj.uz

Submission #110205

# Submission time Handle Problem Language Result Execution time Memory
110205 2019-05-10T07:40:38 Z SamAnd Palembang Bridges (APIO15_bridge) C++17
22 / 100
 140 ms 6636 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int k, n;

long long ans;

vector<int> a;
long long p[N * 2], s[N * 2];

int main()
{
    cin >> k >> n;
    for (int i = 1; i <= n; ++i)
    {
        char xx;
        int x;
        char yy;
        int y;
        cin >> xx >> x >> yy >> y;
        if (xx == yy)
            ans += abs(x - y);
        else
        {
            a.push_back(x);
            a.push_back(y);
        }
    }
    sort(a.begin(), a.end());
    ans += (a.size() / 2);

    for (int i = 1; i < a.size(); ++i)
        p[i] = p[i - 1] + (a[i] - a[i - 1]) * 1LL * i;

    for (int i = a.size() - 2; i >= 0; --i)
        s[i] = s[i + 1] + (a[i + 1] - a[i]) * 1LL * (a.size() - i - 1);

    long long pans = p[0] + s[0];
    for (int i = 1; i < a.size(); ++i)
        pans = min(pans, p[i] + s[i]);

    cout << ans + pans << endl;
    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:33:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i)
                     ~~^~~~~~~~~~
bridge.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < a.size(); ++i)
                     ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 57 ms 4472 KB Output is correct
13 Correct 118 ms 6636 KB Output is correct
14 Correct 81 ms 5192 KB Output is correct
15 Correct 89 ms 4056 KB Output is correct
16 Correct 112 ms 6192 KB Output is correct
17 Correct 117 ms 6608 KB Output is correct
18 Correct 113 ms 6248 KB Output is correct
19 Correct 140 ms 6636 KB Output is correct
20 Correct 123 ms 6224 KB Output is correct
21 Correct 123 ms 6464 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -