oj.uz

Submission #404660

# Submission time Handle Problem Language Result Execution time Memory
404660 2021-05-14T19:29:25 Z sad Palembang Bridges (APIO15_bridge) C++14
22 / 100
 405 ms 26092 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int k,n;ll re=0;
map<ll,int>st,en;
ll no=0,fin=0;
vector<int>v;
int main()
{
    cin>>k>>n;ll w=0;
    for(int i=0;i<n;i++)
    {
        char a,b;
        int x,y;
        cin>>a>>x>>b>>y;
        re+=abs(x-y);
        if(a==b)continue;
        re++;
        if(x>y)swap(x,y);
        v.pb(x);v.pb(y);
        st[x]++;
        st[y];no++;
        en[y]++;w+=x;
    }
    ll mn=1e17;
    ll last=0;
    sort(v.begin(),v.end());
    ll r=0;
    for(auto it:st)
    {
        w+=fin*(it.fi-last);
        w-=no*(it.fi-last);
        fin+=en[it.fi];
        no-=st[it.fi];
        mn=min(mn,w);last=it.fi;

    }
    if(v.size()==0)mn=0;
    re+=2*mn;
    cout<<re;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:31:8: warning: unused variable 'r' [-Wunused-variable]
   31 |     ll r=0;
      |        ^

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 60 ms 1380 KB Output is correct
13 Correct 405 ms 25988 KB Output is correct
14 Correct 127 ms 2488 KB Output is correct
15 Correct 198 ms 15556 KB Output is correct
16 Correct 102 ms 1400 KB Output is correct
17 Correct 230 ms 26032 KB Output is correct
18 Correct 257 ms 26092 KB Output is correct
19 Correct 349 ms 24852 KB Output is correct
20 Correct 110 ms 1332 KB Output is correct
21 Correct 253 ms 26060 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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